개발 학습 블로그입니다.

3 minute read

백준 문제 중 2178번

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

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

풀이

Try1

DFS 로 접근.

이 문제의 핵심은 시간제한내에 문제를 풀이하는 것이다.

DFS로 처음부터 끝까지 도달하는 모든경우를 구해 results에 저장하는 식으로 코드를 짰다.

코드의 흐름은 이렇다.

  • dfs(i,j) 함수 내부에서 dfs(i+1,j), dfs(i,j+1), dfs(i-1,j), dfs(i,j-1) 를 재귀적으로 호출한다.

  • 재귀를 시작하기전 현재 인덱스는 탐색이 되었으므로 현재 인덱스로 돌아오는걸 방지하기 위해서 maze[i][j] = ‘0’ 으로 설정한뒤 DFS를 시작하고 모든 재귀가 종료되면 다시 원래대로 maze[i][j] =’1’ 으로 바꾸어 준다.

  • 위와 마찬가지로 cnt도 재귀를 호출하기전 +1을 해주고 재귀가 끝나면 -1을 해준다.

  • 만약 인덱스가 범위를 벗어나거나 미로에서 ‘1’이 아닌 경우에 return하여 재귀를 종료한다.

이를 코드롤 구현하면 다음과 같다.

from pprint import pprint

n, m = map(int,input().split())

maze = [None]*n
for i in range(n):
    maze[i]=list(input())


cnt = 1
results=[]

def dfs(i,j):

    global cnt

     # 인덱스가 끝에 도달했다면 cnt 를 results에 추가하고 종료
    if i == n-1 and j == m-1:
        results.append(cnt)
        return
    
     # 인덱스가 범위를 벗어나거나 미로가 '1'이 아닌경우 return
    if i<0 or i>n-1 or j<0 or j>m-1 or maze[i][j] != '1':
        return

     # 재귀를 시작할때와 종료할때 처리
    cnt+=1
    maze[i][j] = '0'
    dfs(i+1,j)
    dfs(i,j+1)
    dfs(i-1,j)
    dfs(i,j-1)
    maze[i][j] = '1'
    cnt-=1


dfs(0,0)
print(min(results))

4 6
110110
110110
111111
111101
9

그러나 DFS로 한 풀이는 시간초과가 떴다.

DFS 는 경우에 따라서 최단거리를 구하는 알고리즘에 적합하지 않았다.

Try 2

BFS 로 접근

위에 코드의 방식 그대로 따라가며 DFS를 BFS로 바꾸려고 했는데 DFS 와 BFS의 차이 때문에 cnt에 문제가 생겼다.

DFS에서는 cnt가 처음부터 끝을 도달할때까지 멈추지 않기 때문에 단순하게 cnt를 1씩 증가시켜주면 구할 수 있었는데 BFS 는 탐색중에 되돌아오는 과정이 있어서 조금 다른 방법으로 cnt를 세야 했다.

이 과정이 조금 어려웠는데 약간은 DP의 응용으로 maze 배열의 각 원소에 그 인덱스까지 도달하는데 걸린 최소 칸을 저장하고 다음 인덱스를 계산할때 이전 인덱스들에 1을 더해주는 식으로 해결했다.

  • 큐를 선언하고 시작점은 0,0 이므로 (0,0)을 큐에 넣어준다.

  • 이미 탐색을 완료한 maze[0][0]에 1을 대입해 DP를 위한 배열로 활용한다.

  • 이미 방문한 노드를 표시할 discovered 리스트를 선언한다.

  • 큐가 차있는동안 반복을 시작한다.

  • 만약 v,w 이 최종 목적지인 n-1,m-1에 도달한다면 바로 break로 종료한다.

  • v,w 의 상하좌우 인덱스가 범위를 벗어나지않고, maze가 1이 고, discovered에 존재하지 않을때 q에 [nx,ny]를 추가한다.

  • 그리고 현재 경로까지의 칸을 세기위해 maze[nx][ny] 는 이전 인덱스 v,w의 maze 값 즉 maze[v][w]에 +1을 해준다.

이를 코드로 나타내면 다음과 같다.

from collections import deque

n, m = map(int,input().split())

maze = [None]*n
for i in range(n):
    maze[i]=list(input())


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

def bfs():

    q = deque()
    q.append((0,0))

    discovered = []

    maze[0][0] = 1

    while q:
        v,w = q.popleft()

         # 방문한 노드 표시를 위해 dicoverd에 추가
        

         # 최종 인덱스 도달시 최소 칸수 출력후 종료
        if v == n-1 and w == m-1:
            print(maze[n-1][m-1])
            break

         # 상하좌우 인덱스가 범위를 벗어나지 않고,
         # 아직 방문하지 않았고,
         # 값이 1일 경우에만 실행
        for i in range(4):
            nx, ny = v+dx[i], w+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if ((nx,ny) not in discovered) and maze[nx][ny] == '1':
                    discovered.append((nx,ny))
                    q.append((nx,ny))
                    maze[nx][ny]=maze[v][w]+1 

        

bfs()

4 6
101111
101010
101011
111011
15

배운점

최단경로 문제는 DFS보다는 BFS를 먼저 떠올리자.

Leave a comment

You may also enjoy