[TIL 1/2] 백준 2178 미로탐색(BFS) Python, 프로그래머스 게임 맵 최단거리

나의 초기 설계 (안 좋은 예시)

1. 어제 배운 그래프 형태를 이용해 보려고 했다.

   1. 행, 열의 값들을 순서대로 0번 부터 행*열-1 까지의 번호를 매김
   2. 동서남북 좌표에 조건문을 단다 (-1있거나 행이 행 크기보다 크거나, 열도 마찬가지 등)
   3. 통과한 좌표에 행좌표*열 + 열의 값을 넣는다

2. 깊이 우선이냐 너비 우선이냐 고민

   1. 깊이 우선
   • 도착점에 도달했을 때의 count를 넣어주면 되나
   • 그럼 각 노드에 도달했을 때 count값을 넣어줘야하나
   • 하지만 다른 경로가 더 짧을 수 있는데 조건문 처리를 해줘야해?
   • 너무 별론데? 안 틀릴 자신이 없다
   2. 너비 우선
   • 제일 먼저 도달한 경우의 count를 보내면 간단하겠는데?
   • count는 어떻게 셀까?
   • 도달한 노드의 라인, 그 노드의 level을 파악하면 되겠다.
   • level은 어떻게 파악하나?
   • level이 바뀌기 전 임의 값을 끼워 넣어서 세자

3. 너비 우선으로 결정

나의 부끄러운 코드

• 프로그래머스는 시간 초과!
• 백준에서는 3초라는 놀라운 결과로 통과..사실 상 시간 초과

height, width = map(int, input().split())
maps = [list(map(int, input())) for _ in range(height)]

li = [(0, 1), (1, 0), (0, -1), (-1, 0)]
graph = {x : [] for x in range(width*height)}
for i in range(width*height):
    좌표 = (i//width, i%width)
    if maps[좌표[0]][좌표[1]] == 0:
        continue
    for j in li:
        next_좌표 = (좌표[0]+j[0] , 좌표[1]+j[1])
        if -1 in next_좌표 or width <= next_좌표[1] or height <= next_좌표[0] or maps[next_좌표[0]][next_좌표[1]] == 0:
            continue
        graph[i].append(next_좌표[0]*width + next_좌표[1])

def bfs():
    visited, need_visit = list(), list([0,'x'])
    count = 1
    
    while (len(need_visit) != 1 or need_visit[0] != 'x'):
        x = need_visit.pop(0)
        if x == "x":
            count += 1
            need_visit.append('x')
            continue
        if x in visited:
            continue
        if x == width*height-1:
            break
        visited.append(x)
        need_visit.extend(graph[x])
    return count
        
print(bfs())

오답 노트

• 그래프 형태에 묶인 편협한 생각은 이 문제로 끝(개념만 배우고 문제를 처음 접해서 그런걸로 ㅎㅎ..)
• 아니다 싶은 로직 위에 덧붙이지 말자

옳바른 정답 발상 (사견)

• 방문이 필요한 노드의 동서남북 값을 각각 확인하여 1인 경우에만 (자기자신 값 + 1) 값을 대입하고 방문이 필요한 노드로 append
  • 숫자가 대입된 곳은 무조건 최단거리이다.
  • 0은 막힌 곳이며 1초과의 값이면 이미 방문했던 곳이다.
• 도착지점의 값을 출력

수정 코드

from collections import deque

n, m = map(int, input().split())
maps = [ list(map(int, input())) for _ in range(n) ]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

queue = deque()
count = 0

def bfs(x,y):
    queue.append([x,y])
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                queue.append([nx, ny])
    return maps[n-1][m-1]

print(dfs(0,0))