๐ Problem Solving/Baekjoon
16236๋ฒ: ์๊ธฐ ์์ด
N×N ํฌ๊ธฐ์ ๊ณต๊ฐ์ ๋ฌผ๊ณ ๊ธฐ M๋ง๋ฆฌ์ ์๊ธฐ ์์ด 1๋ง๋ฆฌ๊ฐ ์๋ค. ๊ณต๊ฐ์ 1×1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ํ ์นธ์๋ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์ต๋ 1๋ง๋ฆฌ ์กด์ฌํ๋ค. ์๊ธฐ ์์ด์ ๋ฌผ๊ณ ๊ธฐ๋ ๋ชจ๋ ํฌ๊ธฐ๋ฅผ ๊ฐ
www.acmicpc.net
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
graph = []
for i in range(n):
li = list(map(int, input().split()))
graph.append(li)
for j in range(n):
if li[j] == 9:
graph[i][j] = 2
start = [i, j]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(i, j):
visited = [[0] * n for _ in range(n)]
visited[i][j] = 1
distance = [[0] * n for _ in range(n)]
eat = []
queue = deque()
queue.append((i, j))
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
if graph[nx][ny] <= graph[i][j]:
visited[nx][ny] = 1
distance[nx][ny] = distance[x][y] + 1
queue.append((nx, ny))
if graph[nx][ny] < graph[i][j] and graph[nx][ny] != 0:
eat.append((nx, ny, distance[nx][ny]))
if not eat:
return -1, -1, -1
eat.sort(key=lambda x: (x[2], x[0], x[1]))
return eat[0][0], eat[0][1], eat[0][2]
exp = 0
answer = 0
while True:
i, j = start[0], start[1]
ex, ey, dist = bfs(i, j)
if ex == -1:
break
graph[ex][ey] = graph[i][j]
graph[i][j] = 0
start = [ex, ey]
exp += 1
if exp == graph[ex][ey]:
exp = 0
graph[ex][ey] += 1
answer += dist
print(answer)
ํด์ค
bfs ๋ฌธ์ ๋ค.
๋จน์ ์ ์๋ ๋ฌผ๊ณ ๊ธฐ์ ์์น์ ๊ฑฐ๋ฆฌ๋ฅผ eat์ ์ ์ฅํ๋ค.
lambda๋ฅผ ์ฌ์ฉํด ๊ฑฐ๋ฆฌ, x, y๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ์ฌ ์ฒซ ๋ฒ์งธ ์ธ๋ฑ์ค์ ๋ฐ์ดํฐ๋ฅผ ๋ฆฌํดํ๋ค.
์๋ก์ด ์์ ์์น๋ ํด๋น ์ธ๋ฑ์ค์ x, y ๊ฐ์ด๊ณ , ์๊ธฐ ์์ด์ ์์น๋ฅผ ์๋ก์ด ์์ ์์น๋ก ์ฎ๊ธด๋ค. ์ด ๋, ๊ธฐ์กด ์๊ธฐ ์์ด์ ์์น๋ 0์ผ๋ก ๋ณ๊ฒฝํ๋ค.
์๋ก์ด ์์ ์์น(๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์์ ๋)๊ฐ ๊ฐฑ์ ๋ ๋๋ง๋ค exp๋ฅผ ํ๋์ฉ ๋๋ ค์ฃผ๋ฉฐ ์๊ธฐ ์์ด์ ํฌ๊ธฐ์ ๋น๊ตํ๋ค.
์๊ธฐ ์์ด์ ํฌ๊ธฐ์ exp๊ฐ ๊ฐ๋ค๋ฉด exp๋ 0์ผ๋ก, ์๊ธฐ ์์ด์ ํฌ๊ธฐ๋ ๊ธฐ์กด์ ํฌ๊ธฐ์ 1์ ๋ํด์ค๋ค.
answer์ ๋ฆฌํดํด์ค ๋จน์ ์ ์๋ ๋ฌผ๊ณ ๊ธฐ๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๋ํด์ค๋ค.
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-1629] ๊ณฑ์ / Python (0) | 2021.06.01 |
---|---|
[๋ฐฑ์ค-1991] ํธ๋ฆฌ ์ํ / Python (0) | 2021.06.01 |
[๋ฐฑ์ค-14500] ํ ํธ๋ก๋ฏธ๋ ธ / Python (0) | 2021.05.31 |
[๋ฐฑ์ค-10026] ์ ๋ก์์ฝ / Python (0) | 2021.05.31 |
[๋ฐฑ์ค-11727] 2xn ํ์ผ๋ง 2 / Python (0) | 2021.05.30 |