[알고리즘/BFS & DFS] 2178번 : 미로 탐색 - python

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

2178번: 미로 탐색

 

---

• 문제
• 소요시간: 35분 실패

---

• 설계하기(접근방법) 

1. 입력받기

행렬을 입력받는다

 

2. 구현하기

bfs로 풀면 쉬운 문제였다

dfs로 풀었다가 최저 해를 보장할 수 없는 상황이 발생해서 틀렸다

 

bfs를 구현해서 가장 최단거리를 계산한다

 

3. 출력하기

최단거리를 계산한다

 

---

• 코드(출력)

from collections import deque

def bfs (x,y):
    dx = [1, -1, 0, 0]
    dy = [0 ,0 ,-1, 1]
    q = deque()
    q.append([x,y])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0 <= ny < m:
                if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append([nx,ny])
    return visited[n-1][m-1]



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

a = bfs(0,0)
print(a)

---

• 얻어갈 부분

1. dfs를 사용할지, bfs를 사용할지 미리 생각하고 구현하자