[Python] 3197: 백조의 호수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import sys
from collections import deque
 
r, c = map(int, sys.stdin.readline().rstrip().split())
arr = []  # board
visited = [[0* c for _ in range(r)]  # 방문한 곳에 조상 남기는 리스트
l_list = []
water_queue = deque([])
dy = [0011]
dx = [1100]
 
 
def main():
    for i in range(r):
        arr.append(list(sys.stdin.readline().rstrip()))
 
    for i in range(r):
        for j in range(c):
            if arr[i][j] == ‘L’:
                l_list.append((i, j))
                water_queue.append((i, j))
                continue
            if arr[i][j] == ‘.’:
                water_queue.append((i, j))
 
    print(bfs())
 
 
def bfs():
    day = 0
    l_queue = deque([l_list[0]])
 
    while True:
        n_queue = deque()
        while l_queue:
            y, x = l_queue.popleft()
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
 
                if l_list[1== (ny, nx):
                    return day
 
                if 0 <= nx < c and 0 <= ny < r and not visited[ny][nx]:
                    visited[ny][nx] = True
                    if arr[ny][nx] == ‘.’:
                        l_queue.append((ny, nx))
                    else:
                        n_queue.append((ny, nx))
 
        l_queue = n_queue
        length = len(water_queue)
        for i in range(length):
            y, x = water_queue.popleft()
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
 
                if 0 <= nx < c and 0 <= ny < r and arr[ny][nx] != ‘.’:
                    water_queue.append((ny, nx))
                    arr[ny][nx] = ‘.’
        day += 1
 
 
main()
 
cs

관련글

제목 작성자 작성일