BFS/DFS 정복기 -memoization을 이용한 효율적인 탐색-

1. 문제

 

1861. 정사각형 방

 

ttps://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE&problemTitle=정사각형+방&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

$n^{2}$개의 방이 $N*N$ 형태로 늘어서있고, 각각은 1부터 $n^{2}$이하까지 전부 서로 다른 수로 순서와 무관하게 적혀있다.

 

어떤 방에 있을때, 정확히 현재 방보다 1 더 큰 수가 적힌 방으로만 이동할 수 있다고 할때,

 

처음에 어떤 수가 적힌 방에 있어야 가장 많이 이동할 수 있을까?

 

 

2. 풀이

 

일반적인 BFS/DFS로 탐색을 수행하는데, 완전탐색법으로 모든 방에서 시작을 해봐서 얼마나 많이 이동할 수 있을지 비교해보면 될 것이다

 

이동하는 조건은 현재 방에 적힌 수보다 1 더 큰 수로 이동하면 된다

 

근데 이 문제에서 핵심적으로 이해해야할 트릭은, "정확히 현재 방보다 1 더 큰 수가 적힌 방으로만 이동"이다.

 

이 부분을 잘 생각해본다면,

 

예를 들어 위와 같은 배열에서 3에서 시작해서 이동을 했다고 해보자.

 

3 > 4 > 5까지 이동하고 더 이상 이동을 못할텐데

 

그렇다면 이제 다음에 검사할 시작 지점은 4일 것이다.

 

하지만 4는 어디까지 이동할 수 있을까??

 

 

당연히 3에서 이동할때보다 더 적은 4 > 5만 이동 가능하다

 

마찬가지로 5를 검사할 차례가 온다면, 이 5는 검사할 필요가 있을까?? 굳이 안봐도 3보다 더 적을 것이기 때문에 검사할 필요가 없다

 

그래서 모든 방에서 탐색을 시작하는데, 하나의 visited 배열을 만들자

 

그러면 방에 방문할때마다 방문한 지점을 visited에 표시해두고, 이미 표시된 지점은 다시 검사할 필요가 없다.

 

왜냐하면, 이전에 나온 최댓값을 가진 경로에 반드시 속할것이기 때문에

 

위와 같이 9부터 시작을 한다면, 9, 3>4>5, 6>7, 1, 8, 2 이렇게 탐색을 하고 최대 길이가 3에서 시작해서 3이라고 끝나야 한다

 

4번자리에 1말고 6이 있었다면 다른거 아니냐??

 

아니다, 그렇다면 이미 3에서 3>4>5>6으로 탐색을 하고 5에서 시작을 한다고 하면? 5>6밖에 못갈거야

 

 

2-1) BFS 코드

 

시작 큐에 시작지점, 이동거리까지 저장해두고 현재 시작지점도 출력해야해서 시작지점 start = maps[y][x]로 저장해두자

 

4방탐색을 수행하는데, 정확히 1 더 큰 방으로만 이동가능하므로 maps[dy][dx] == maps[y][x] + 1이라는 조건도 추가

 

이동가능하면 현재 이동거리 d에서 d+1을 큐에 넣어주고

 

이동하면 최댓값은 항상 d+1로 갱신해준다

 

visited는 위에서 설명했듯이 memoization을 위한 용도로, 검사할 필요가 없는 지점을 체크하기 위한 용도

 

bfs함수를 구성하면, 입력을 받고 visited 배열을 만들고, 시작지점,최댓값을 초기화

 

모든 시작점에서 완전 검색을 수행하는데 bfs를 수행하면서 visited에 1이라고 표시된 값이라면 검사할 필요가 없고, 1이 아닌 지점만 검사하면 된다.

 

그렇게 나온 최댓거리, 최소 시작지점을 갱신해나간다

 

from collections import deque

def bfs(x,y,n,maps,visited):

    queue = deque([(x,y,1)])
    
    start = maps[y][x]

    max_distance = 0

    while queue:
        
        x,y,d = queue.popleft()

        for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
            
            dx = x + ni
            dy = y + nj

            if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1 and (maps[dy][dx] == maps[y][x] + 1):
                
                queue.append((dx,dy,d+1))
                    
                max_distance = d+1
                
                visited[dy][dx] = 1
                    
    return start,max_distance,visited
                
T = int(input())

for t in range(1,T+1):

    n = int(input())

    maps = [list(map(int,input().split())) for _ in range(n)]
    
    visited = [[0]*n for _ in range(n)]

    max_distance = 0

    min_start = n*n+1

    for y in range(n):
        
        for x in range(n):
            
            if not visited[y][x]:
                
                visited[y][x] = 1
            
                start,distance,visited = bfs(x,y,n,maps,visited)

                if max_distance < distance:

                    max_distance = distance
                    min_start = start

                elif max_distance == distance:

                    if min_start > start:

                        min_start = start
     
    print('#'+str(t),*[min_start,max_distance])

 

귀찮아서 최댓값 갱신 작업을 다음과 같이 쓴다면?

 

if max_distance <= distance:

    max_distance = distance
    min_start = start
    
    if min_start > start:

        min_start = start

 

최소 시작지점은, 최대 거리가 서로 같을때, 시작지점이 더 적은 값을 구해야하는건데

 

위와같이 쓴다면, 최댓값이 서로 다르더라도 최소 시작지점으로 갱신하기때문에 다른 답이 나온다

 

 

2-2) DFS 코드

 

동일한 로직으로 DFS로도 가능하다

 

visited를 memoization 용도로 탐색된 곳은 더 검사할 필요가 없이 이미 최댓값보다 적은 경로기 때문에 visited에 표시되지 않은 방만 탐색하도록 만들고

 

모든 dfs 재귀적 경로 탐색이 끝나고(for문이 끝나고) 나온 d를 max_d로 갱신해줘야한다는 점 

 

    for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
        
        dx = x + ni
        dy = y + nj

        if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1 and (maps[dy][dx] == maps[y][x] + 1):
            
            dfs(dx,dy,n,d+1,maps,visited)
    
    if max_d < d:
        
        max_d = d

    return max_d,visited

 

for문 끝나면 더 이상 탐색을 수행하지 못하고 있다는 뜻이고, 그럴때 나온 최종 거리가 d이고 이것을 max_d로 갱신해줘야한다는 점..을 조금 생각해야함

 

def dfs(x,y,n,d,maps,visited):
    
    global max_d
    
    visited[y][x] = 1

    for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
        
        dx = x + ni
        dy = y + nj

        if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1 and (maps[dy][dx] == maps[y][x] + 1):
            
            dfs(dx,dy,n,d+1,maps,visited)
    
    if max_d < d:
        
        max_d = d

    return max_d,visited
                
T = int(input())

for t in range(1,T+1):

    n = int(input())

    maps = [list(map(int,input().split())) for _ in range(n)]
    
    visited = [[0]*n for _ in range(n)]

    max_distance = 0

    min_start = n*n+1

    for y in range(n):
        
        for x in range(n):
            
            if not visited[y][x]:
                
                start = maps[y][x]

                max_d = 0
                            
                distance,visited = dfs(x,y,n,1,maps,visited)

                if max_distance < distance:

                    max_distance = distance
                    min_start = start

                elif max_distance == distance:

                    if min_start > start:

                        min_start = start
     
    print('#'+str(t),*[min_start,max_distance])