[DFS, BFS] 백준 1987번: 알파벳 *** / 골드4

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

<처음 시간 초과 났던 코드>

x_lim, y_lim = map(int, input().split())
graph = []
for i in range(x_lim):
    graph.append(input())

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

def dfs(x,y,count, visited):
    global answer
    if graph[x][y] in visited:
        answer = max(answer, count)
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < x_lim and 0 <= ny < y_lim:
            dfs(nx, ny, count+1, visited+[graph[x][y]])

answer=1
dfs(0,0,0,[])
print(answer)

<위 코드랑 동일하지만 다른 방식>

x_lim, y_lim = map(int, input().split())
graph = []
for i in range(x_lim):
    graph.append(input())

visited = []

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

def dfs(x,y,count):
    global answer
    if graph[x][y] in visited:
        answer = max(answer, count)
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < x_lim and 0 <= ny < y_lim:
            visited.append(graph[x][y])
            dfs(nx, ny, count+1)
            visited.pop()
answer=1
dfs(0,0,0)
print(answer)

 

dfs시 방문 알파벳 체크를 해야하는데 백트래킹 시 이 흔적을 지워줘야 한다. 다른 깊이 탐색에서 이 흔적때문에 영향을 받게 되면 안되기 때문이다.

첫번째 코드 - dfs(nx, ny, count+1, visited+[graph[x][y]])을 넘겨주는 방식으로 구현,

그러나 리스트를 더해주는 형태가 아닐 경우 이 방식은 사용할 수 없다. 즉 보편적 방식이 아니다.

두번째 코드 - visited.append(graph[x][y]),  dfs(nx, ny, count+1),  visited.pop() 형태와 같이

백트래킹 시에 흔적을 지워주는 방식으로 구현 -> 좀 더 보편적인 방식

 

 

어쨌든 위의 코드들은 백트래킹 체크 시에 시간이 걸려서 시간 초과가 난 듯하다.

 

<정답 코드>

x_lim, y_lim = map(int, input().split())
graph = []
for i in range(x_lim):
    graph.append([ord(x)-65 for x in input()])

visited = [0]*26

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

def dfs(x,y,count):
    global answer
    if visited[graph[x][y]] == 1:
        answer = max(answer, count)
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < x_lim and 0 <= ny < y_lim:
            visited[graph[x][y]] = 1
            dfs(nx, ny, count+1)
            visited[graph[x][y]] = 0

answer = 1
dfs(0,0,0)
print(answer)

질문 목록을 참고하여 알파벳 문자를 아스키 코드로 고치는 법을 배웠다.

visited 리스트를 알파벳 개수만큼 생성해주고 방문 알파벳은 1을 채워넣는 방식으로 코드를 개선했다.

이러면 백트래킹 체크 시간이 훨씬 짧아진다.

 

대신 백트래킹이 되고 나서는 다시 해당 알파벳의 visited 값을 0으로 바꿔줘야 한다.

다른 dfs에서 영향을 받으면 안되기 때문에!