백준 문제 풀이 - 그래프 탐색
📰 문제
문제 확인 🏃
💡 입출력 예제
15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
>>
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 343 3
2 0 0
0 0 1
0 1 1
>>
0 0 0
0 0 -1
0 -1 -1💬 풀이
🎵 첫번째 풀이
from collections import deque
import sys
input = sys.stdin.readline
R, C = map(int, input().split()) # 행, 열
graph = [list(map(int, input().split())) for _ in range(R)]
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
def solution():
answer = [[0] * C for _ in range(R)]
start = [(r, c) for r in range(R) for c in range(C) if graph[r][c] == 2] # 탐색 시작 위치 찾기 (2)
queue = deque()
queue.append((start[0][0], start[0][1], 0))
graph[start[0][0]][start[0][1]] = 0
while queue:
r, c, count = queue.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if nr < 0 or nc < 0 or nr >= R or nc >= C or not graph[nr][nc]:
continue
queue.append((nr, nc, count+1))
answer[nr][nc] = count+1
graph[nr][nc] = 0
for r in range(R):
for c in range(C):
if graph[r][c] == 1:print(-1, end = " ")
else: print(answer[r][c], end = " ")
print()
solution()
🎵 두번째 풀이
from collections import deque
import sys
input = sys.stdin.readline
R, C = map(int, input().split()) # 행, 열
graph = [list(map(int, input().split())) for _ in range(R)]
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
def solution():
start = [(r, c) for r in range(R) for c in range(C) if graph[r][c] == 2] # 탐색 시작 위치 찾기 (2)
queue = deque()
queue.append((start[0][0], start[0][1]))
graph[start[0][0]][start[0][1]] = 2
while queue:
r, c = queue.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if nr < 0 or nc < 0 or nr >= R or nc >= C or graph[nr][nc] is not 1:
continue
queue.append((nr, nc))
graph[nr][nc] = graph[r][c] + 1
for r in range(R):
for c in range(C):
if graph[r][c] == 1: print(-1, end = " ")
elif graph[r][c] == 0: print(0, end = " ")
else: print(graph[r][c]-2, end = " ")
print()
solution()
✒️ 생각
문제를 잘 읽자.....가지 못한 곳은 -1!!!
🐥 Backend Developer 🐥