๐ Problem Solving/Baekjoon
https://www.acmicpc.net/problem/7576
7576๋ฒ: ํ ๋งํ
์ฒซ ์ค์๋ ์์์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ๋ ์ ์ M,N์ด ์ฃผ์ด์ง๋ค. M์ ์์์ ๊ฐ๋ก ์นธ์ ์, N์ ์์์ ์ธ๋ก ์นธ์ ์๋ฅผ ๋ํ๋ธ๋ค. ๋จ, 2 ≤ M,N ≤ 1,000 ์ด๋ค. ๋์งธ ์ค๋ถํฐ๋ ํ๋์ ์์์ ์ ์ฅ๋ ํ ๋งํ
www.acmicpc.net
from collections import deque
n, m = map(int, input().split())
graph = []
for _ in range(m):
graph.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
def bfs():
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= m or ny >= n:
continue
if graph[nx][ny] == 0:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
for i in range(m):
for j in range(n):
if graph[i][j] == 1:
queue.append((i, j))
bfs()
isTrue = False
answer = -2
for i in graph:
for j in i:
if j == 0:
isTrue = True
answer = max(answer, j)
if isTrue == True:
print(-1)
else:
print(answer - 1)
ํด์ค
์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ๋ ์ ์ผ ์ฌ๋ฐ๋ ํํธ๊ฐ BFS ๋ฌธ์ ๋ค.
ํ ๋งํ ๊ฐ ์๋ ์์น๋ค์ ๋จผ์ deque์ ์ ์ฅํ๊ณ ๋์ BFS๋ฅผ ์ํํ๋ค. ์ฒ์์ ์ด ๋ถ๋ถ์ ์บ์นํ์ง ๋ชปํด์ ํ๋ ธ๋ค..๐
ํ ๋งํ ๊ฐ ์๋ ์์น๋ก๋ถํฐ ์ ์ ํผ์ ธ๋๊ฐ๋ฉด์ ์ต์ ํ ๋งํ ๊ฐ ์๊ธฐ๊ธฐ ๋๋ฌธ์ ๋ฏธ๋ฆฌ deque์ ์ต์ ํ ๋งํ ์์น๋ฅผ ์ ์ฅํด์ผ ํ๋ค.
BFS๋ฅผ ๋ชจ๋ ์ํํ๊ณ ๋์ graph ๋ฆฌ์คํธ์ 0์ด ์์ผ๋ฉด ์์ต์ ํ ๋งํ ๊ฐ ์๋ ๊ฒ์ด๋ฏ๋ก flag๋ฅผ True๋ก ํ๊ณ -1์ ์ถ๋ ฅํ๋ค. ํ ๋งํ ๊ฐ ์ ๋ถ ์ต์๋ค๋ฉด graph ๋ฆฌ์คํธ์ ์ต๋๊ฐ - 1์ ์ถ๋ ฅํ๋ค
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-11656] ์ ๋ฏธ์ฌ ๋ฐฐ์ด / Python (0) | 2021.05.18 |
---|---|
[๋ฐฑ์ค-10825] ๊ตญ์์ / Python (0) | 2021.05.17 |
[๋ฐฑ์ค-10610] 30 / Python (0) | 2021.05.17 |
[๋ฐฑ์ค-1697] ์จ๋ฐ๊ผญ์ง / Python (0) | 2021.05.17 |
[๋ฐฑ์ค-1475] ๋ฐฉ๋ฒํธ / Python (0) | 2021.05.17 |