[Python] λ°±μ€ 3184 μ (BFS)


π λ¬Έμ
λ―Έν€μ λ·λ§λΉμλ νΉμ μμ μμ΄ μλ€. κ·Έκ° νΉ μ λ μ¬μ΄μ λ°°κ³ ν λλλ λ§λΉμ λ€μ΄μ μμ 곡격νλ€.
λ§λΉμ νκ³Ό μ΄λ‘ μ΄λ£¨μ΄μ§ μ§μ¬κ°ν λͺ¨μμ΄λ€. κΈμ '.' (μ )μ λΉ νλλ₯Ό μλ―Ένλ©°, κΈμ '#'λ μΈν리λ₯Ό, 'o'λ μ, 'v'λ λλλ₯Ό μλ―Ένλ€.
ν μΉΈμμ μν, μμ§λ§μΌλ‘ μ΄λνλ©° μΈν리λ₯Ό μ§λμ§ μκ³ λ€λ₯Έ μΉΈμΌλ‘ μ΄λν μ μλ€λ©΄, λ μΉΈμ κ°μ μμ μμ μν΄ μλ€κ³ νλ€. λ§λΉμμ "νμΆ"ν μ μλ μΉΈμ μ΄λ€ μμμλ μνμ§ μλλ€κ³ κ°μ£Όνλ€.
λ€νν μ°λ¦¬μ μμ λλμκ² μΈμμ κ±Έ μ μκ³ μμ μμ μμ μκ° λλμ μλ³΄λ€ λ§λ€λ©΄ μ΄κΈ°κ³ , λλλ₯Ό μ°λ¦¬μμ μ«μλΈλ€. κ·Έλ μ§ μλ€λ©΄ λλκ° κ·Έ μ§μ μμ λͺ¨λ μμ λ¨Ήλλ€.
맨 μ²μ λͺ¨λ μκ³Ό λλλ λ§λΉ μ μμμ μ‘΄μ¬νλ€.
μμΉ¨μ΄ λλ¬νμ λ μ΄μλ¨μ μκ³Ό λλμ μλ₯Ό μΆλ ₯νλ νλ‘κ·Έλ¨μ μμ±νλΌ.
μ λ ₯
첫 μ€μλ λ μ μ Rκ³Ό Cκ° μ£Όμ΄μ§λ©°(3 ≤ R, C ≤ 250), κ° μλ λ§λΉμ νκ³Ό μ΄μ μλ₯Ό μλ―Ένλ€.
λ€μ Rκ°μ μ€μ Cκ°μ κΈμλ₯Ό κ°μ§λ€. μ΄λ€μ λ§λΉμ ꡬ쑰(μΈν리, μ, λλμ μμΉ)λ₯Ό μλ―Ένλ€.
μΆλ ₯
νλμ μ€μ μμΉ¨κΉμ§ μ΄μμλ μκ³Ό λλμ μλ₯Ό μλ―Ένλ λ μ μλ₯Ό μΆλ ₯νλ€.
μμ μ λ ₯ 1
6 6
...#..
.##v#.
#v.#.#
#.o#.#
.###.#
...###
μμ μΆλ ₯ 1
0 2
μμ μ λ ₯ 2
8 8
.######.
#..o...#
#.####.#
#.#v.#.#
#.#.o#o#
#o.##..#
#.v..v.#
.######.
μμ μΆλ ₯ 2
3 1
μμ μ λ ₯ 3
9 12
.###.#####..
#.oo#...#v#.
#..o#.#.#.#.
#..##o#...#.
#.#v#o###.#.
#..#v#....#.
#...v#v####.
.####.#vv.o#
.......####.
μμ μΆλ ₯ 3
3 5
π νμ΄
π¬ Code
import sys
from collections import deque
input = sys.stdin.readline
def bfs(x, y):
q = deque([(x, y)])
o = 0
v = 0
while q:
x, y = q.popleft()
for i in range(5):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
if graph[nx][ny] == '#':
continue
elif graph[nx][ny] == 'v':
v += 1
elif graph[nx][ny] == 'o':
o += 1
q.append((nx, ny))
visited[nx][ny] = 1
return o, v
if __name__ == '__main__':
n, m = map(int, input().split())
graph = []
visited = [[0 for _ in range(m)] for _ in range(n)]
for _ in range(n):
graph.append(list(input().rstrip()))
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]
sheep, wolf = 0, 0
for i in range(n):
for j in range(m):
if not visited[i][j] and graph[i][j] != '#':
s, w = bfs(i, j)
if s > w:
sheep += s
else:
wolf += w
print(sheep, wolf)
π‘ Solution
- graph: λ§λΉ μν
- visited: ν΄λΉ μ’νμ λ°©λ¬Ένλμ§ μ²΄ν¬νλ 2μ°¨μ λ°°μ΄
for i in range(n):
for j in range(m):
if not visited[i][j] and graph[i][j] != '#':
s, w = bfs(i, j)
if s > w:
sheep += s
else:
wolf += w
(0, 0)λΆν° μ’ν 체ν¬λ₯Ό λ립λλ€. λ§μ½ (0, 0)μ μμ§ λ°©λ¬Ένμ§ μμκ³ μ΄ μ’νμ λμ¬μλ κ²μ΄ μΈνλ¦¬κ° μλλΌλ©΄ bfs(0, 0)μ μνν©λλ€. bfs ν¨μμμλ ν μμμ μ’νλ₯Ό λͺ¨λ λ°©λ¬Ένλ©΄μ μκ³Ό λλμ μλ₯Ό 리ν΄ν©λλ€. 2μ€ forλ¬Έμμλ μ΄ λ¦¬ν΄κ°μ λ°μμ μκ³Ό λλμ μΈμ κ²°κ³Όλ₯Ό 쑰건문μΌλ‘ 체ν¬νκ³ μ΄μλ¨μ μκ³Ό λλμ μλ₯Ό μ λ°μ΄νΈν©λλ€.
+) μ²μμλ λ°©ν₯벑ν°μ μνμ’μ°λ§ λ£μμλλ°,
.#.
#o#
.#.
μ²λΌ μΈν리 μ¬μ΄μ ν λ§λ¦¬λ§ λλ¬μΈμ¬ μλ κ²½μ°μλ ν΄λΉ μ’νλ₯Ό 체ν¬νμ§ λͺ»νκ³ μ΄λμ’νλ§ μ²΄ν¬ν΄μ λμ΄κ°κΈΈλ λ°©ν₯벑ν°μ μ μ리λ μΆκ°ν΄μ€¬μ΅λλ€.