[한개라도 제대로] DFS&BFS(1) - 백준 2178번 미로 탐색

문제

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

풀이

1. 논리적인 순서 확정

입력1: 미로를 만들기 위한 행(N), 열(M)의 수
입력2: 줄바꿈(개행문자)을 기준으로 행의 수(N)만큼 추가적으로 입력을 하는데, 각 입력에는 열의 갯수(M)만큼의 숫자를 입력한다.

출력: 시작점부터 N,M까지 최단경로를 지나는 정점의 갯수 출력

이 미로문제를 격자형 그래프로 바라봤을때, 시작점부터 종착지까지 그래프의 연결노드 갯수(vertex)*_가 출력하고자하는 값과 동일함을 알수있다.
*_격자형 그래프를 만들기 위해서는, 처음 시작하는 점에서 인접한 정점이 1일 경우 간선(Edge)을 만들어 줄 수 있다.
먼저, 격자형 그래프를 만들고 격자형 그래프를 만들게 되면 하나의 연결요소를 만들 수 있으니까 문제가 원하는 최단거리는 각 연결노드의 숫자를 Following 하면 이 문제를 풀 수 있을것이다.

2. 필요한 자료연산 리스트업

1) 격자형 그래프를 만들기
2) 그래프 탐색문제를 풀기
(탐색문제: 시작점에서 간선을 0개 이상 사용해서 갈 수 있는 정점들은 무엇인가?)

3. 이에 제일 유리한 자료구조 선택

1) 탐색문제를 푸는 알고리즘은 DFS,BFS가 있다. 그 중 BFS 알고리즘을 사용할 것이다.
시간은 O(V+E)만큼 소요될것이고, 공간 또한 O(V+E)만큼 할당될것이다.

4. 구현

고려해야할것

1. 방문한 노드인지 아닌지 체크
2. 미로 영역을 벗어날 경우 제외
3. 1인경우 queue에 삽입

from collections import deque
import sys

n, m = list(map(int, sys.stdin.readline().split()))
maze = []
for i in range(n):
    maze.append(list(map(int, sys.stdin.readline().rstrip())))
visited = [[False] * m for _ in range(n)] # 이렇게 해야한다.

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
que = deque()
que.append((0, 0))
visited[0][0] = True

def bfs(n,m,que, visited, maze):
    result = []
    while(que):
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if ny < 0 or n <= ny or nx < 0 or m <= nx: # 미로 영역을 벗어날 경우 제외
                continue
            if not visited[ny][nx] and maze[ny][nx] > 0: # 방문한 노드인지 아닌지 체크 & 1인경우 queue에 삽입
                que.append((nx, ny))
                visited[ny][nx] = True
                maze[ny][nx] = maze[y][x] + 1
                if ny == n-1 and nx == m-1:
                    result.append(maze[ny][nx])
    return result

result = bfs(n,m,que, visited, maze)
print(min(result))

알게된점

1. 격자형 그래프에서 어떤것이 x이고 어떤것을 y로 둘지 명확하게 해두어야 한다.
2. visited = [[False] * m] * n
   처럼 하게 되면 약한 복사형태(soft copy)로 들어간다. 그래서 visited[1][0] = 1로 하게 되면 1열 전체가 바뀌어진다.
3. if문을 사용할때 Out of list 에러가 나올 수 있음에 주의한다.

5. 좋은 코드에서 학습하기

류호석님의 코드를 통해 학습하자.링크

import sys
from collections import deque
si = sys.stdin.readline
n, m = list(map(int, si().split()))
a = [si().strip() for _ in range(n)]

dist = [[0] * m for _ in range(n)]
dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]

def bfs():
    queue = deque()
    queue.append(0)
    queue.append(0)
    dist[0][0] = 1

    while queue:
        x = queue.popleft()
        y = queue.popleft()
        for dx, dy in dir:
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
            if dist[nx][ny] != 0: continue
            if a[nx][ny] == '0': continue
            dist[nx][ny] = dist[x][y] + 1
            queue.append(nx)
            queue.append(ny)

bfs()
print(dist[n - 1][m - 1])

배울점

1. 입력받을때 간단하게, 처음에
   si = sys.stdin.readline으로 하고
   n,m = list(map(int, si().split()) 하는것이 좀더 이해하기 쉬운거같다.
2. 행과 열데이터 추가 입력할때
   a = [si().strip() for _ in range(n)] 하는것이 for문으로 2줄하는것보다 직관성 측면에서 더 좋은거 같다.
3. dist\[x\]\[y\]를 visited 용도이자, 거리를 계산하는 용도로 사용하셨다.
   그래프와 거리를 계산하는 그래프를 확실히 나누는것이 더 좋을것 같다.
4. 고려해야할 점을 간단하게 처리했다.
   범위를 벗어나거나, 방문했던곳이나, 정점의 값이 0 인경우 따로 나눠서 처리했다.