[BOJ 1987] 알파벳 (Python)

www.acmicpc.net/problem/1987

1987번: 알파벳

 

r, c=map(int, input().split())
graph=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visited=[[False]*c for _ in range(r)]
alphabet=[False]*26
result=0

for _ in range(r):
    graph.append(input())

def dfs(x, y, count):
    global result
    visited[x][y]=True
    alphabet[ord(graph[x][y])-ord('A')]=True
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<r and 0<=ny<c and visited[nx][ny]==False and alphabet[ord(graph[nx][ny])-ord('A')]==False:
            dfs(nx, ny, count+1)
            visited[nx][ny]=False
            alphabet[ord(graph[nx][ny])-ord('A')]=False
    result=max(result, count)
    return result

dfs(0,0,1)
print(result)

 

어려워서 구글링해서 해답 찾은 뒤 풀었던.. 문제.. (역시 골드의 벽은 넘사였다)

분석을 해보자면, DFS 문제다. 여기서 필요한 포인트를 정리하면

• 알파벳 반복을 막기 위해 해당 알파벳이 쓰였음을 나타내는 배열이 필요하다: alphabet
• DFS 탐색을 할 때 조건을 만족하면( 1. 인덱스가 범위를 넘지 않고,2. 알파벳이 한번도 쓰이지 않았고, 3. 미방문 상태일때), DFS 함수를 재귀 호출할 때 count+1을 하여 횟수를 저장한다.
• DFS 함수가 호출이 종료되고 원래 호출된 위치로 돌아올 때, 방문->미방문, 알파벳 사용->알파벳 미사용으로 바꿔줘야한다. 그렇게 해줘야지만 다음 탐색을 해서 최대값을 찾을 수 있다.
• 해당 인덱스에서 dfs 탐색이 종료될 경우 count 값과 result 값을 비교해서 최대값을 계속 찾아준다.

재귀는 (내 기준에서) 짜기가 좀 까다롭다. 아직 연습이 덜 되어서인가. DFS는 1. 탐색 조건 2. 리턴할 때 어떻게 이 2가지를 중점적으로 보도록 하자.