728x90
출처 : https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
< 초기설정 >
n, m = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
graph = []
for i in range(n):
graph.append(list(map(int, input())))
count = 0
queue = [[0, 0]]
< bfs 정의 >
def bfs():
while queue:
a, b = queue.pop(0)
for i in range(4):
x = a + dx[i]
y = b + dy[i]
if 0 <= x < n and 0 <= y < m and graph[x][y] == 1:
graph[x][y] = graph[a][b] + 1
queue.append([x, y])
< 답 출력 >
bfs()
print(graph[-1][-1])
< 전체코드 >
n, m = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
graph = []
for i in range(n):
graph.append(list(map(int, input())))
count = 0
queue = [[0, 0]]
def bfs():
while queue:
a, b = queue.pop(0)
for i in range(4):
x = a + dx[i]
y = b + dy[i]
if 0 <= x < n and 0 <= y < m and graph[x][y] == 1:
graph[x][y] = graph[a][b] + 1
queue.append([x, y])
bfs()
print(graph[-1][-1])728x90
'코딩' 카테고리의 다른 글
| [BOJ] 백준 2667 파이썬 - 단지번호 붙이기 (0) | 2021.11.17 |
|---|