πŸ’» Algorithm/Python

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

μ„ μ£Ό 2022. 7. 2. 15:49

 

πŸ“Œ 문제

λ―Έν‚€μ˜ λ’·λ§ˆλ‹Ήμ—λŠ” νŠΉμ • 수의 양이 μžˆλ‹€. κ·Έκ°€ ν‘Ή μž λ“  사이에 λ°°κ³ ν”ˆ λŠ‘λŒ€λŠ” λ§ˆλ‹Ήμ— 듀어와 양을 κ³΅κ²©ν–ˆλ‹€.

 

λ§ˆλ‹Ήμ€ ν–‰κ³Ό μ—΄λ‘œ 이루어진 μ§μ‚¬κ°ν˜• λͺ¨μ–‘이닀. κΈ€μž '.' (점)은 빈 ν•„λ“œλ₯Ό μ˜λ―Έν•˜λ©°, κΈ€μž '#'λŠ” μšΈνƒ€λ¦¬λ₯Ό, '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#
.#.

처럼 μšΈνƒ€λ¦¬ 사이에 ν•œ 마리만 λ‘˜λŸ¬μ‹Έμ—¬ μžˆλŠ” κ²½μš°μ—λŠ” ν•΄λ‹Ή μ’Œν‘œλ₯Ό μ²΄ν¬ν•˜μ§€ λͺ»ν•˜κ³  μ΄λ™μ’Œν‘œλ§Œ μ²΄ν¬ν•΄μ„œ λ„˜μ–΄κ°€κΈΈλž˜ λ°©ν–₯벑터에 μ œμžλ¦¬λ„ μΆ”κ°€ν•΄μ€¬μŠ΅λ‹ˆλ‹€.