[๋ฐฑ์ค-2468] ์์ ์์ญ / Python
๐ Problem Solving/Baekjoon
from collections import deque
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
maxCnt = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque()
queue.append([x, y])
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and temp[nx][ny] == 0:
temp[nx][ny] = 1
queue.append([nx, ny])
for i in range(101):
temp = [[0] * n for i in range(n)]
cnt = 0
for j in range(n):
for k in range(n):
if graph[j][k] <= i:
temp[j][k] = 1
for j in range(n):
for k in range(n):
if temp[j][k] == 0:
temp[j][k] = 1
bfs(j, k)
cnt += 1
if cnt == 0:
break
maxCnt = max(maxCnt, cnt)
print(maxCnt)
ํด์ค
๋ฑํ ์ด๋ ต์ง ์์ BFS ๋ฌธ์ ์๋ค. ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์์ญ์ 0์ผ๋ก ์ค์ ํ๊ณ BFS๋ฅผ ์งํํ๋ฉด์ ์์ญ์ ๊ฐ์๋ฅผ ์ธ๋ฉด ๋๋ค.
๋ชจ๋ ์์ญ์ด ๋ฌผ์ ์ ๊ธฐ๋ ๋์ด์์ ํ์์ ๋ฉ์ถฐ์ค๋ค.
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-1074] Z / Python (0) | 2021.05.25 |
---|---|
[๋ฐฑ์ค-7569] ํ ๋งํ / Python (0) | 2021.05.23 |
[๋ฐฑ์ค-2583] ์์ญ ๊ตฌํ๊ธฐ / Python (0) | 2021.05.22 |
[๋ฐฑ์ค-13549] ์จ๋ฐ๊ผญ์ง 3 / Python (0) | 2021.05.21 |
[๋ฐฑ์ค-1916] ์ต์๋น์ฉ ๊ตฌํ๊ธฐ / Python (0) | 2021.05.20 |