๐ฑ ๋ฌธ์
๐ฑ ํ์ด
์งํ์ด๊ฐ ๋ฏธ๋ก์์ ํ์ถํ ์ ์๋ ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ธ๋ฐ, ๋ถ๋ ๊ฐ์ด ์ฌ๋ฐฉ์ผ๋ก ํ์ฐํ๊ธฐ ๋๋ฌธ์ ์์ง์ด๋ ๊ฐ์ฒด๊ฐ 2๊ฐ์ธ BFS ๋ฌธ์ ์ ๋๋ค.
1. ๋ฏธ๋ก ์ ๋ณด์ ์งํ์ด์ ๋ถ์ ์ด๊ธฐ ์์น ์ ๋ณด
์ฐ์ ๋ฏธ๋ก ์ ๋ณด๋ฅผ graph
์ ์ ์ฅํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ graph
์์ ์งํ์ด์ ์ด๊ธฐ ์์น("J"
)์ ๋ถ์ ์ด๊ธฐ ์์น("F"
)๋ฅผ ๊ฐ๊ฐ jihoon_start
์ fire_start
์ ์ ์ฅํฉ๋๋ค.
h, w = map(int, input().split())
visited = [[False] * w for _ in range(h)]
graph = []
for _ in range(h):
graph.append(list(input())[:w])
fire_start = []
for i in range(h):
for j in range(w):
if graph[i][j] == "J":
jihoon_start = (i, j)
graph[i][j] = 0
elif graph[i][j] == "F":
fire_start.append((i, j))
2. ๋ถ์ ํ์ฐ ์ ๋ณด ์ ์ฅํ๊ธฐ
์๊ฐ์ด ์ง๋ ๋์ ๋ถ์ด ๋จผ์ ํ์ฐ๋๊ณ ํ์ฐ๋ ๊ณณ์๋ ์งํ์ด๊ฐ ์ด๋ํ ์ ์๊ธฐ ๋๋ฌธ์ ๋ถ์ ํ์ฐ ์ ๋ณด๋ฅผ ๋ฏธ๋ฆฌ ์ ์ฅํฉ๋๋ค.
def fire_bfs(start):
global graph, w, h
fire = deque([])
visited = [[False] * w for _ in range(h)]
for s in start:
y, x = s
fire.append((y, x))
visited[y][x] = True
while fire:
y, x = fire.popleft()
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if ny < 0 or nx < 0 or ny > h - 1 or nx > w - 1:
continue
if visited[ny][nx] == False and graph[ny][nx] != "#":
graph[ny][nx] = graph[y][x] + "F"
visited[ny][nx] = True
fire.append((ny, nx))
fire_bfs(fire_start)
- ๋ถ์ ๋งค ์๊ฐ๋ง๋ค ์ฌ๋ฐฉ(์, ์๋, ์ผ์ชฝ, ์ค๋ฅธ์ชฝ)์ผ๋ก ํ์ฐ๋๊ธฐ ๋๋ฌธ์ bfs ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด ํ์ฐ ์ ๋ณด๋ฅผ ์ ์ฅํฉ๋๋ค.
- ๋ถ์ ํ์ฐ ์ ๋ณด๋ ์๊ฐ ์ ๋ณด์ ํจ๊ป ์ ์ฅ๋์ด์ผ ํ๊ธฐ ๋๋ฌธ์ ์ ๋ ์๊ฐ์ด ์ง๋ ์๋ก F์ ๊ฐ์๋ฅผ ๋๋ ค์ graph์ ์ ์ฅํด์ฃผ์์ต๋๋ค.
- ์๋ฅผ ๋ค์ด ์์ ๊ฐ์ ์์์์ fire_bfs์ ํจ์๊ฐ return๋ ๋ค, graph์ ๊ฒฐ๊ณผ๋ ์์ ๊ฐ์ต๋๋ค. ๋ฐ๋ผ์ F์ ๊ฐ์๋ก ๋ถ์ด ํ์ฐ๋ ์๊ฐ ์ ๋ณด๋ฅผ ํ์ ํ ์ ์์ต๋๋ค.
3. ์งํ์ด ์ด๋์ํค๊ธฐ
์ด์ ์งํ์ด๋ฅผ ์ด๋์ํฌ ์ฐจ๋ก์ ๋๋ค. ์งํ์ด๋ ๋ง์ฐฌ๊ฐ์ง๋ก ์ฌ๋ฐฉ์ผ๋ก ์ด๋ ๊ฐ๋ฅํ๊ธฐ ๋๋ฌธ์ bfs ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํฉ๋๋ค.
def jihoon_bfs(start):
global graph, w, h
y, x = start
jihoon = deque([(y, x)])
graph[y][x] = 0
visited = [[False] * w for _ in range(h)]
visited[y][x] = True
while jihoon:
y, x = jihoon.popleft()
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if ny < 0 or nx < 0 or ny > h - 1 or nx > w - 1:
return graph[y][x] + 1
if visited[ny][nx] == False and graph[ny][nx] != "#":
if graph[ny][nx] == "." or graph[ny][nx].count("F") - 1 > graph[y][x] + 1:
visited[ny][nx] = True
jihoon.append((ny, nx))
graph[ny][nx] = graph[y][x] + 1
return -1
- ์ด ๋, ์ด๋๊ฐ๋ฅํ ๊ฒฝ์ฐ๋ฅผ
graph[ny][nx]
๊ฐ"."
์ผ ๋์ ๋ถ์ด ํ์ฐ๋ ์๊ฐ(graph[ny][nx].count("F") - 1
)๋ณด๋ค ์งํ์ด์ ํ์ฌ ์ด๋ ์๊ฐ(graph[y][x] + 1
)์ด ์์ ๋๋ก ํฉ๋๋ค. ny
,nx
๊ฐgraph
์ ๋ฒ์๋ฅผ ๋ฒ์ด๋๋ฉด ์งํ์ด๊ฐ ํ์ถํ๋ค๋ ์๋ฏธ์ด๋ฏ๋ก ์ต๋จ ๊ฒฝ๋ก(graph[y][x] + 1
)์ ๋ฆฌํดํ๊ณ , ์งํ์ด๊ฐ ์ด๋ํ ์ ์๋ ๊ฒฝ์ฐ๋ฅผ ๋ชจ๋ ํ์ํ์์๋graph
๋ฅผ ๋ฒ์ด๋์ง ๋ชปํ๋ค๋ฉด ํ์ถ์ ๋ชปํ๋ค๋ ์๋ฏธ์ด๋ฏ๋ก-1
์ returnํฉ๋๋ค.
๐ฑ ์ ๋ต ์ฝ๋
# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 4179 ๋ถ!
import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
visited = [[False] * w for _ in range(h)]
graph = []
for _ in range(h):
graph.append(list(input())[:w])
fire_start = []
for i in range(h):
for j in range(w):
if graph[i][j] == "J":
jihoon_start = (i, j)
graph[i][j] = 0
elif graph[i][j] == "F":
fire_start.append((i, j))
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
answer = 0
def fire_bfs(start):
global graph, w, h
fire = deque([])
visited = [[False] * w for _ in range(h)]
for s in start:
y, x = s
fire.append((y, x))
visited[y][x] = True
while fire:
y, x = fire.popleft()
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if ny < 0 or nx < 0 or ny > h - 1 or nx > w - 1:
continue
if visited[ny][nx] == False and graph[ny][nx] != "#":
graph[ny][nx] = graph[y][x] + "F"
visited[ny][nx] = True
fire.append((ny, nx))
def jihoon_bfs(start):
global graph, w, h
y, x = start
jihoon = deque([(y, x)])
graph[y][x] = 0
visited = [[False] * w for _ in range(h)]
visited[y][x] = True
while jihoon:
y, x = jihoon.popleft()
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if ny < 0 or nx < 0 or ny > h - 1 or nx > w - 1:
return graph[y][x] + 1
if visited[ny][nx] == False and graph[ny][nx] != "#":
if graph[ny][nx] == "." or graph[ny][nx].count("F") - 1 > graph[y][x] + 1:
visited[ny][nx] = True
jihoon.append((ny, nx))
graph[ny][nx] = graph[y][x] + 1
return -1
fire_bfs(fire_start)
answer = jihoon_bfs(jihoon_start)
if answer > -1:
print(answer)
else:
print("IMPOSSIBLE")
'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] #15486 ํด์ฌ2 (Python, Dynamic Programming, ์๊ฐ ์ด๊ณผ ํด๊ฒฐ) (0) | 2023.10.15 |
---|---|
[BOJ] #2758 ๋ก๋ (Python, Dynamic Programming) (1) | 2023.10.14 |
[BOJ] #15649) N๊ณผ M(1) (Python, Back tracking) (1) | 2023.10.01 |
[BOJ] 11729 ํ๋ ธ์ด ํ ์ด๋ ์์ (Python, Recursion) (0) | 2023.09.30 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๊ด๋ฌผ ์บ๊ธฐ (Python, ๊ตฌํ) (0) | 2023.09.30 |
๋๊ธ