πŸ’» Algorithm/Python

[Python] λ°±μ€€ 2178 미둜 탐색 (BFS)

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

 

πŸ“Œ 문제

N×M크기의 λ°°μ—΄λ‘œ ν‘œν˜„λ˜λŠ” λ―Έλ‘œκ°€ μžˆλ‹€.

 

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1


λ―Έλ‘œμ—μ„œ 1은 이동할 수 μžˆλŠ” 칸을 λ‚˜νƒ€λ‚΄κ³ , 0은 이동할 수 μ—†λŠ” 칸을 λ‚˜νƒ€λ‚Έλ‹€. μ΄λŸ¬ν•œ λ―Έλ‘œκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, (1, 1)μ—μ„œ μΆœλ°œν•˜μ—¬ (N, M)의 μœ„μΉ˜λ‘œ 이동할 λ•Œ μ§€λ‚˜μ•Ό ν•˜λŠ” μ΅œμ†Œμ˜ μΉΈ 수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. ν•œ μΉΈμ—μ„œ λ‹€λ₯Έ 칸으둜 이동할 λ•Œ, μ„œλ‘œ μΈμ ‘ν•œ 칸으둜만 이동할 수 μžˆλ‹€.

 

μœ„μ˜ μ˜ˆμ—μ„œλŠ” 15칸을 μ§€λ‚˜μ•Ό (N, M)의 μœ„μΉ˜λ‘œ 이동할 수 μžˆλ‹€. 칸을 μ…€ λ•Œμ—λŠ” μ‹œμž‘ μœ„μΉ˜μ™€ 도착 μœ„μΉ˜λ„ ν¬ν•¨ν•œλ‹€.

μž…λ ₯

첫째 쀄에 두 μ •μˆ˜ N, M(2 ≤ N, M ≤ 100)이 μ£Όμ–΄μ§„λ‹€. λ‹€μŒ N개의 μ€„μ—λŠ” M개의 μ •μˆ˜λ‘œ λ―Έλ‘œκ°€ μ£Όμ–΄μ§„λ‹€. 각각의 μˆ˜λ“€μ€ λΆ™μ–΄μ„œ μž…λ ₯으둜 μ£Όμ–΄μ§„λ‹€.

좜λ ₯

첫째 쀄에 μ§€λ‚˜μ•Ό ν•˜λŠ” μ΅œμ†Œμ˜ μΉΈ 수λ₯Ό 좜λ ₯ν•œλ‹€. 항상 λ„μ°©μœ„μΉ˜λ‘œ 이동할 수 μžˆλŠ” 경우만 μž…λ ₯으둜 μ£Όμ–΄μ§„λ‹€.

예제 μž…λ ₯ 1

4 6
101111
101010
101011
111011

예제 좜λ ₯ 1

15

예제 μž…λ ₯ 2

4 6
110110
110110
111111
111101

예제 좜λ ₯ 2

9

예제 μž…λ ₯ 3

2 25
1011101110111011101110111
1110111011101110111011101

예제 좜λ ₯ 3

38

예제 μž…λ ₯ 4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 좜λ ₯ 4

13

 


 

πŸ“Œ 풀이

πŸ’¬ Code

import sys
from collections import deque
input = sys.stdin.readline


def bfs(x, y):
    q = deque([(x-1, y-1)])
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1:
                q.append((nx, ny))
                maze[nx][ny] += maze[x][y]

    return maze[n-1][m-1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    maze = []

    for _ in range(n):
        maze.append(list(map(int, input().rstrip())))
	
    # λ°©ν–₯벑터 (상, ν•˜, 쒌, 우)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    print(bfs(1, 1))

 

πŸ’‘ Solution

μ΄μ½”ν…Œμ—μ„œ 예제둜 λ‚˜μ™”λ˜ 문제라 μ‰½κ²Œ ν’€μˆ˜ μžˆμ—ˆμŠ΅λ‹ˆλ‹€.

 

  1. μ’Œν‘œκ°€ μ£Όμ–΄μ§€λ©΄ ν•΄λ‹Ή μ’Œν‘œμ˜ μƒν•˜μ’Œμš° μ’Œν‘œλ‘œ 이동할 수 μžˆλŠ”μ§€ 각각 μ²΄ν¬ν•˜κΈ° μœ„ν•΄ μ’Œν‘œλ§ˆλ‹€ for문을 4번 λŒλ¦½λ‹ˆλ‹€.
  2. nx, nyλŠ” μ΄λ™μ’Œν‘œλ₯Ό λ‚˜νƒ€λ‚Έλ‹€. μ΄λ™μ’Œν‘œκ°€ (-1, -1)처럼 μ’Œν‘œλ₯Ό λ²—μ–΄λ‚˜μ§€ μ•Šμ•˜κ³  ν•΄λ‹Ή μ’Œν‘œμ— 놓인 값이 1이라면 κ·Έ 곳으둜 이동할 수 μžˆλŠ” κ²ƒμ΄λ―€λ‘œ 이동 ν›„ 큐에 (nx, ny)μŒμ„ λ„£μ–΄μ€λ‹ˆλ‹€.
  3. μ§€λ‚˜μ•Ό ν•˜λŠ” μ΅œμ†Œ 칸수λ₯Ό ꡬ해야 ν•˜λ―€λ‘œ 이동할 λ•Œλ§ˆλ‹€ μ΄λ™μΉΈμˆ˜λ₯Ό λˆ„μ μ‹œν‚΅λ‹ˆλ‹€. maze[x][y]μ—μ„œ maze[nx][ny]둜의 μ΄λ™μΉΈμˆ˜λŠ” 1칸인데, maze[nx][ny]의 값이 이미 1이기 λ•Œλ¬Έμ— maze[nx][ny] += maze[x][y] ν•΄μ£Όλ©΄ maze[nx][ny]에 μ—¬νƒœκΉŒμ§€ μ§€λ‚˜μ˜¨ μΉΈμˆ˜κ°€ μž…λ ₯λ©λ‹ˆλ‹€.
  4. λͺ©ν‘œ μ’Œν‘œμ˜ 값을 좜λ ₯ν•΄μ£Όλ©΄ 끝!