[dfs/백준] 1987번 : 알파벳

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

 

지나온 길에 있던 알파벳들을 저장할 리스트가 있어야 중복 알파벳을 지나지 않는다 

집합에 조건 만족하는 원소 넣고, dfs 진행한 다음 그 원소를 제거한다 

dfs진행하다 중복된 알파벳을 마주친 경우 탐색을 멈추고, 그간의 길이 중 최댓값을 answer에 저장한다 

 

- 정답 풀이 :

n,m=map(int,input().split())
data=[list(input()) for _ in range(n)]

dx=[-1,1,0,0]
dy=[0,0,-1,1]
process=set()
answer=0

def dfs(x,y,count):
    global answer
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if data[nx][ny] not in process:
                process.add(data[nx][ny])
                dfs(nx,ny,count+1)
                process.remove(data[nx][ny])
            else:
                answer=max(answer,count)
                
process.add(data[0][0])
dfs(0,0,1)                
print(answer)

 

- 시도해 본 풀이 : 

 

처음에는 각 깊이 마다 리스트를 가져가서 비교하려고 했는데, 이렇게 하면

하나의 깊이만 진행되고, 다음 깊이를 진행할 때 process 리스트가 유지돼서 틀린 답을 출력한다 

 

n,m=map(int,input().split())
data=[list(input()) for _ in range(n)]

dx=[-1,1,0,0]
dy=[0,0,-1,1]

answer=0
def dfs(x,y,process):
    global answer
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if data[nx][ny] not in process:
                process.append(data[nx][ny])
                dfs(nx,ny,process)
            else:
                answer=max(answer,len(process))
                
process=[data[0][0]]
dfs(0,0,process)                
print(answer)