1. 문제
https://www.acmicpc.net/problem/2178
2. 풀이 과정
방법1) deque 라이브러리 활용하기
from collections import deque
n, m = map(int, input().split())
miro = [list(map(int, input())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
#BFS => 최단 거리
def bfs(graph):
q = deque()
q.append((0, 0))
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))
print(graph[n-1][m-1])
bfs(miro)
방법2) 리스트 자료형에 제공되는 메서드 이용
n, m = map(int, input().split())
miro = [list(map(int, input())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
#BFS => 최단 거리
def bfs(graph):
q = []
q.append((0, 0))
while q:
x, y = q[0]
x, y = q.pop(0)
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))
print(graph[n-1][m-1])
bfs(miro)
방법3) 문자열로 받아와서 그대로 사용하기 - int로 바꾸는 연산 사용하지 않음
n, m = map(int, input().split())
miro = [list(input()) for _ in range(n)]
miro[0][0] = 1
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
#BFS => 최단 거리
def bfs(graph):
q = [(0, 0)]
while q:
x, y = q[0]
x, y = q.pop(0)
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))
print(graph[n-1][m-1])
bfs(miro)
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Python_DFS&BFS] 백준 14502번 : 연구소 (0) | 2021.08.09 |
---|---|
[Python_DFS&BFS] 백준 7576번 : 토마토 (0) | 2021.08.07 |
[Python_Greedy] 백준 1789번 : 수들의 합 (0) | 2021.08.04 |
[Python_Greedy] 백준 2217번 : 로프 (0) | 2021.08.03 |
[Python_Greedy] 백준 1541번 : 잃어버린 괄호 (0) | 2021.08.02 |