[백준/Python] 2178번(BFS)_미로 탐색

📌문제 유형

그래프 이론, 그래프 탐색, BFS (실버1)

 

📌문제

2178번: 미로 탐색

 

📌나의 문제풀이

- 성공

from collections import deque

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

maps = []
for _ in range(n):
    rows = list(map(int,input()))
    maps.append(rows)

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

while q:
    x,y = q.popleft()

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

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):
            if maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                q.append([nx,ny])

print(maps[n-1][m-1])

 

- 실패

import sys
sys.setrecursionlimit(10000)

n,m = map(int,input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int,input())))


def dfs_min(graph,x,y) :    # 사방에서 작은 값 찾기
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    num_list = []

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] not in [0,1]:
            num_list.append(graph[nx][ny])
    if len(num_list) > 0:
        return min(num_list)
    else:
        return 1


def dfs(graph,x,y):   # 시작점
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    if x == n-1 and y == m-1:
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if (nx == n-1 and ny == m-1):
                graph[nx][ny] = dfs_min(graph,nx,ny) + 1

            if graph[nx][ny] == 1 :
                graph[nx][ny] += dfs_min(graph,nx,ny)   # 사방에 있는 것들 확인해야 함
                dfs(graph,nx,ny)

dfs(graph,0,0)
print(graph[n-1][m-1])

 

📌 다른사람의 문제풀이

[BOJ/백준] 2178번 미로 탐색 (Python 파이썬)

from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

# 2차원 리스트 생성
graph = [list(map(int, ' '.join(input().split()))) for _ in range(N)]

queue = deque([(0, 0)])

# 미로 문제 풀 때는 이동을 표현해준다.
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
cnt = 0

# BFS
while queue:
    x, y = queue.popleft()
    for i in range(4):
        next_x, next_y = x+dx[i], y+dy[i]
        if 0 <= next_x < N and 0 <= next_y < M:  # 범위 확인
            if graph[next_x][next_y] == 1:  # 경로 확인
                queue.append((next_x, next_y))
                graph[next_x][next_y] = graph[x][y] + 1  # value 자체를 이동 횟수로 사용

print(graph[N-1][M-1])

 

📌 리뷰 

- BFS는 q.popleft() 사용해야 맨 앞 숫자가 나옴!

- BFS 이용이라고 생각해놓고 DFS로 코드 짬...

- DFS 코드를 BFS로 바꾸면 통과 가능

- BFS, DFS 특징

 DFS가 유리한 경우
- 재귀적인 특징과 백트래킹을 이용하여 모든 경우를 하나씩 전부 탐색하는 경우
- Graph의 크기가 클 경우
- Optimal한 답을 찾는 것이 아닌 경우
- 경로의 특징을 저장해야 하는 경우 ex) 경로의 가중치, 이동 과정에서의 제약

BFS가 유리한 경우
- 최단 거리 or 최단 횟수 구하는 경우
- Optimal한 답을 찾는 경우, BFS는 가장 처음 발견되는 해답이 최단 거리이다!
- 탐색의 횟수를 구해야 하는 경우(7576번 토마토 문제)

출처 : https://great-park.tistory.com/m/46