DFS도 재귀보다는 반복문으로 구현 연습하기1

1. 문제

 

1987번: 알파벳 (acmicpc.net)

1987번: 알파벳

 

2. 풀이1

 

기본적인 DFS문제긴한디 분명히 맞는데 시간초과에 애먹었다..

 

from sys import stdin

def dfs(x,y,s):
    
    global answer
    
    for i in range(4):
        
        dx = x + d[i][0]
        dy = y + d[i][1]

        if dx >= 0 and dx <= c-1 and dy >= 0 and dy <= r-1:
            
            if alpha[maps[dy][dx]] == 1:
                
                if answer < s:
                    
                    answer = s
                    
                    if answer == 26:
                        return
                
                continue
            
            alpha[maps[dy][dx]] = 1
            
            dfs(dx,dy,s+1)
            
            alpha[maps[dy][dx]] = 0
            
r,c = map(int,stdin.readline().split())

maps = [list(map(lambda x: ord(x) - 65, stdin.readline().rstrip())) for _ in range(r)]    

alpha = [0]*26

alpha[maps[0][0]] = 1

answer = 1

d = [[1,0],[0,1],[-1,0],[0,-1]]

dfs(0,0,1)

print(answer)

 

그래도 나름 최적화? 잡기술을 배우긴 했는데

 

일단 그동안 4방향 탐색할때 이렇게 썼는데..

 

for a,b in [[1,0],[0,1],[-1,0],[0,-1]]:

    dx = x + a
    dy = y + b

 

왜인지 모르겠지만? 얘는 시간초과나고 다음과 같이 바꾸면 통과함

 

앞으로 이렇게 쓰자고

 

d =  [[1,0],[0,1],[-1,0],[0,-1]]

for i in range(4):

    dx = x + d[i][0]
    dy = y + d[i][1]

 

이게 결정적인것 같고.. 

 

이 문제는 특별한게 이전에 밟은 알파벳은 또 못밟기 때문에.. 사실 조금만 생각하면 map에 대한 visited 배열은 필요없고

 

그동안 밟아온 알파벳에 대한 정보를 visited로 가지고 있으면 충분하다

 

알파벳은 1~26까지 가능하니까 크기 26인 alpha배열을 선언하여 visited로 활용함

 

그러다보니 최댓값은 26까지만 가능하고, answer = 26인 순간 더 이상 탐색할 필요가 없거든.. return으로 재귀를 끊도록

 

            if alpha[maps[dy][dx]] == 1:
                
                if answer < s:
                    
                    answer = s
                    
                    if answer == 26:
                        return
                
                continue

 

그리고 매번 숫자로 바꾸지 말라고.. 미리 maps를 숫자로 바꾼 배열로 구성하긴 했음

 

maps = [list(map(lambda x: ord(x) - 65, stdin.readline().rstrip())) for _ in range(r)]    

alpha = [0]*26

alpha[maps[0][0]] = 1

 

큰 의미 없긴 했는데.. 굳이 안바꿔도 이렇게 써도 통과하긴 했거든

 

from sys import stdin

def dfs(x,y,s):
    
    global answer
    
    n = ord(maps[y][x]) - ord('A') + 1

    if alpha[n] == 1:
        
        if answer < s:
            
            answer = s

        return
    
    alpha[n] = 1
    
    for i in range(4):
        
        dx = x + d[i][0]
        dy = y + d[i][1]

        if dx >= 0 and dx <= c-1 and dy >= 0 and dy <= r-1:

            dfs(dx,dy,s+1)
    
    alpha[n] = 0


r,c = map(int,stdin.readline().split())

maps = [stdin.readline().rstrip() for _ in range(r)]    

alpha = [0]*27

answer = 0

d = [[1,0],[0,1],[-1,0],[0,-1]]

dfs(0,0,0)

print(answer)

 

3. 반복문으로 DFS 구현하기

 

나는 7초 정도 걸리는데 다른 사람들은 0.2초 정도에 통과하는거 보니 stack을 이용한 반복문 DFS로 통과하더라고

 

stack 반복문으로 바꾸는 기본 방법은

 

https://deepdata.tistory.com/383

DFS 알고리즘 유형별 기본 틀 정리

 

일단 조건에 맞으면 stack에 전부 집어넣고,

 

stack에서 빼면서 visited 방문 처리를 해서 continue 시키는 방식으로..

 

근데 visited 배열 필요 없다는 관찰을 했고, 어떤 알파벳을 지났는지 가지고 있어야하는데

 

스택에 (x,y,길이,지나온 알파벳들)로 담아서 dfs를 수행

 

from sys import stdin

def convert(x,y):

    return ord(maps[y][x]) - ord('A') + 1

def dfs(x,y):

    stack = [(0,0,1,maps[y][x])]

    d = [[0,1],[1,0],[0,-1],[-1,0]]

    answer = 0

    while stack:

        x,y,t,alpha = stack.pop()

        if answer < t:

            answer = t

        if answer == 26:

            break

        for i in range(4):

            dx = x + d[i][0]
            dy = y + d[i][1]

            if dx >= 0 and dx <= c-1 and dy >= 0 and dy <= r-1:

                if maps[dy][dx] not in alpha:

                    stack.append((dx,dy,t+1,alpha+maps[dy][dx]))

    return answer

r,c = map(int,stdin.readline().split())

maps = [stdin.readline() for _ in range(r)]

print(dfs(0,0))

 

근데 visited를 어디서 체크해야할지 모르겠더라고...

 

지나간 경로는 stack에 들어간 하나의 원소들마다 나타내고 있는데...

 

걍 다음 위치 dx,dy에 있는 알파벳 maps[dy][dx]가 현재 경로 alpha에 없으면 stack에 넣는 방식으로 했는데

 

4초나 걸리던데??

 

문자열 덧셈이나 in연산이 느리다고 해도 최대 26자라 큰 차이 없을거고

 

다른 사람들과 무슨 차이가 있나 생각을 해보고 그러니 역시 visited로 굳이 안가봐도 될 장소에 또 가서 

 

탐색을 하는게 시간을 많이 쓰는 원인이라고 생각했는데

 

조금만 더 생각을 해보니...

 

어떤 위치 (x,y)에 그동안 지나온 알파벳 path로 도착을 했다고 치자.

 

 

 

그러면 (x,y)에서 DFS로 탐색하고 나서, stack에 계속 쌓일건데...

 

그런데 다른 위치 (z,w) 등등을 탐색하고 나서 stack에서 제거하고 나니...

 

또 (x,y)에 대응하는 path가 나왔다.

 

그러면 이걸 또 DFS로 4방향 탐색을 해야하는가?

 

 

이전에 (x,y)에 path로 도달하고, DFS를 수행해봤으니.. 또 (x,y)에 path로 도달한다면.. 이전에 계산해봤던 결과를

 

또 계산하게 될거잖아..

 

 

 

DFS니까 한 방향을 쭉 탐색하다보니.. 다른 방향을 탐색할때는 이전에 탐색해뒀던 방향 정보랑은 무관하게 탐색하니까

 

또 계산하게 되어 중복 계산이 되어가지고 여기서 시간 차이가 발생한다 이 말이지

 

 

즉, visited를 maps와 동일한 크기로 만들어놓고, 각 좌표 (x,y)마다 어떠한 경로 alpha로 도달했는지 저장해둔다.

 

stack에서 pop하면서 매 DFS마다 visited[y][x] == alpha라면, 이미 그 방향은 이전에 계산해봤으니까

 

굳이 하지 마라고 skip한다면.. 엄청난 시간 이득을 본다

 

from sys import stdin

def convert(x,y):

    return ord(maps[y][x]) - ord('A') + 1

def dfs(x,y):

    stack = [(0,0,maps[y][x])]
    visited = [[0]*c for _ in range(r)]

    d = [[0,1],[1,0],[0,-1],[-1,0]]

    answer = 0

    while stack:

        x,y,alpha = stack.pop()

        if answer < len(alpha):

            answer = len(alpha)

        if answer == 26:

            break
        
        if visited[y][x] == alpha:
            continue
        
        visited[y][x] = alpha

        for i in range(4):

            dx = x + d[i][0]
            dy = y + d[i][1]

            if dx >= 0 and dx <= c-1 and dy >= 0 and dy <= r-1:

                if maps[dy][dx] not in alpha:

                    stack.append((dx,dy,alpha+maps[dy][dx]))

    return answer

r,c = map(int,stdin.readline().split())

maps = [stdin.readline() for _ in range(r)]

print(dfs(0,0))