https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 BFS를 잘 숙지하고 암기하고 있다면 실버 1 티어라는 높은 난이도에도 불구하고 매우 쉽게 해결할 수 있는 문제였습니다. 1은 이동할 수 있는 칸이고 0은 이동할 수 없는 칸입니다. 또한 인접한 칸 즉 상, 하, 좌, 우 의 방향으로 이동하기 때문에 행, 열의 리스트를 각각 만들어서 다음과 같이 정의합니다.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1 ,1]
위 처럼 정의하면 i = 0인 경우 (-1, 0) 즉 위쪽 방향(상), i = 1인 경우 (1, 0) 즉 아래쪽 방향(하), i = 2인 경우 (0, -1) 즉 좌측 방향(좌), i = 3인 경우 (0, 1) 즉 우측 방향(우)으로 for문을 이용하여 쉽게 해결할 수 있습니다.
문제 해결을 위한 팁
위 문제의 경우 visited 리스트를 따로 정의하지 않아도 해결할 수 있습니다. 출발지와 도착지를 출발한 개수를 구하라고 하였기 때문에 bfs과정에서 방문하지 않은 그래프를 탐색하는것이 아닌 graph[nx][ny] == 1을 탐색하고 이 경우 이전 좌표의 그래프 값에 1을 더한 값으로 재 정의해줌으로써 방문처리 및 탐색하는 칸의 개수를 한 번에 해결할 수 있습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(start):
xPos = start[0]
yPos = start[1]
q = deque()
q.append((xPos, yPos))
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 graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
q.append((nx, ny))
bfs((0, 0))
print(graph[n-1][m-1])
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 2606: 바이러스(Python) (0) | 2021.01.25 |
|---|---|
| 백준 알고리즘 2667: 단지번호붙이기 (Python) (0) | 2021.01.25 |
| 백준 알고리즘 1260: DFS와 BFS (Python) (0) | 2021.01.19 |
| 백준 알고리즘 2810: 컵홀더 (Python) (0) | 2021.01.19 |
| 백준 알고리즘 13305: 주유소(Python) (0) | 2021.01.19 |