Algorithem/백준 PS with code
백준 #14940 - [S1] 쉬운 최단거리 : BFS, Queue
jamong5
2023. 6. 7. 23:58
(python3)
14940번: 쉬운 최단거리
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이
www.acmicpc.net
큐를 활용한 BFS 로 최단거리 구하기
시작점에서부터 다른 점들까지의 최단 거리를 구하는 문제이기 때문에 너비 우선 탐색으로 진행하면 해결할 수 있습니다. BFS 는 큐를 활용해서 구현하는게 가장 대표적입니다.
기본 아이디어는, 탐색을 진행할때마다 새로운 탐색 지점들을 큐에 넣고, 큐에서 지점을 하나씩 빼서 그 지점의 다음 단계 탐색을 진행하는걸 반복하는 겁니다. 그러면 깊이가 깊은 노드들이 큐의 뒷쪽으로 쌓이면서 bfs 를 수행할 수 있게 됩니다.
파이썬 collections 의 deque 에 구현되어있는 덱 자료구조를 사용했습니다. 덱 자료구조는 FI, LI, FO, LO 을 자유롭게 구사할 수 있어서 큐와 스택을 모두 수행할 수 있는 자료구조 입니다.
코드
import sys
from collections import deque
def solution(input) :
# bfs, 위치 저장
# 입력받기
R,C = list(map(int,input().split()))
MAP = []
for _ in range(R) :
MAP.append(list(map(int,input().split())))
dist_map = [[-1 for _ in range(C)] for _ in range(R)]
D = [(-1,0),(1,0),(0,-1),(0,1)]
def inicialize_and_find_2() :
r2,c2 = 0,0
for r in range(R) :
for c in range(C) :
if MAP[r][c] == 2 :
r2,c2 = r,c
elif MAP[r][c] == 0 :
dist_map[r][c] = 0
return r2,c2
def bfs(r,c) :
deq = deque([(r,c,0)])
dist_map[r][c] = 0
while deq :
r,c,lev = deq.popleft()
for dr, dc in D :
nr = r+dr
nc = c+dc
if nr >= 0 and nr < R and nc >= 0 and nc < C :
if MAP[nr][nc] == 1 and dist_map[nr][nc] == -1 :
dist_map[nr][nc] = lev+1
deq.append((nr,nc,lev+1))
r,c = inicialize_and_find_2()
bfs(r,c)
for r in range(R) :
print(' '.join(str(i) for i in dist_map[r]))
input = sys.stdin.readline
solution(input)
my solved.ac :
solved.ac
알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다.
solved.ac