[백준/dfs] 1987: 알파벳

-문제:https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

처음에는 bfs로 풀어야할 것 같아 풀어보려고 했으나 depth를 구하기 어려울 것 같아서 dfs로 풀어야되겠다고 생각했다 

이동하는 것까지는 구현하겠는데, 탈출 조건을 어떻게 해야할지 몰랐다. 

탈출조건으로 생각한게 주변에 있는 문자들이 모두 result에 있는 문자들이면 반환되는 것을 생각했다. 이렇게 탈출한 result의 길이를 구하면된다고 생각했지만 틀린 생각이었다 

 

dfs는 x,y,cnt 3가지의 파라미터로 진행을 한다. x,y는 2차원 행렬에서의 위치를 의미하고, cnt는 depth를 의미하는 것 같다 

앞으로 깊이를 구하는 문제에서 cnt 파라미터를 추가해서 진행해야겠다고 생각했다 

여기서 global ans를 선언해서 (x,y)까지의 깊이 중 최댓값을 저장한다 

result.remove(s[nx][ny])가 중요한데, 만약 최대 칸 수가 아닌 경우 돌아가기 위해서이다(백트래킹 과정)

함수를 시작하기 위한 초기값을 result에 추가하고 dfs를 진행한다 

 

 

-정답풀이: 

r,c=map(int,input().split())
s=[list(input()) for _ in range(r)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
result=set()
ans=0
def dfs(x,y,cnt):    
    global ans
    ans=max(ans,cnt)
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<r and 0<=ny<c:
            if s[nx][ny] not in result:
                result.add(s[nx][ny])
                dfs(nx,ny,cnt+1)
                result.remove(s[nx][ny])
                
result.add(s[0][0])                                                      
dfs(0,0,1)
print(ans)