[백준][파이썬]3197번 - 백조의 호수

문제

 

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

---

https://jeinalog.tistory.com/18

Python｜탐색 알고리즘 뿌시기 (1) DFS, BFS 의 개념과 구현

진짜 쉽게 잘 설명해 놓으신 글..!!

 

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

ex, ey, ans = 0, 0, 0   #ex와 ey는 다른 백조 하나의 위치,ans는 날짜
dx, dy = (0, -1, 0, 1), (-1, 0, 1, 0)   #상하좌우 방향을 의미
R, C = map(int, input().split())   #행과 열 입력
a = [list(input().strip()) for _ in range(R)]
wc = [[False]*C for _ in range(R)]
sc = [[False]*C for _ in range(R)]
wq1, wq2 = deque(), deque()   #양방향 큐 2개 생성
sq1, sq2 = deque(), deque()

def water():
    while wq1:
        x, y = wq1.popleft()   #왼쪽에서 pop
        a[x][y] = '.'
        for i in range(4):   #상하좌우 4번 진행
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= R or ny < 0 or ny >= C or wc[nx][ny]:
                continue   #nx가 0보다 작거나 R보다 크거나 같으면 넘어간 것을 의미, ny도 마찬가지(인덱스 번호)
            if a[nx][ny] == '.':   #물이 있다면 wq1에 추가
                wq1.append((nx, ny))
            else:   #물이 없다면 wq2에 추가
                wq2.append((nx, ny))
            wc[nx][ny] = True

def swan():
    while sq1:
        x, y = sq1.popleft()
        if x == ex and y == ey:   #백조끼리 만나면 true를 리턴
            return True
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= R or ny < 0 or ny >= C or sc[nx][ny]:
                continue
            if a[nx][ny] == '.':
                sq1.append((nx, ny))
            else:
                sq2.append((nx, ny))
            sc[nx][ny] = True
    return False

for i in range(R):
    for j in range(C):
        if a[i][j] == 'L':   #백조의 위치 설정
            if not sq1:   #sq1의 큐가 없다면, 백조 한 마리의 위치를 추가
                sq1.append((i, j))
                sc[i][j] = True
            else:   #나머지 백조의 위치를 ex와 ey에 저장(도착지로 사용)
                ex, ey = i, j
            a[i][j] = '.'   #백조의 위치도 물을 의미
        if a[i][j] == '.':   #물을 wq1에 추가
            wq1.append((i, j))
            wc[i][j] = True   #물의 위치를 true로 변경
while True:
    water()
    if swan():   #백조가 만나면 true를 return하므로 while문을 break
        break
    wq1 = wq2   #다음 날이 되어 다음 빙판을 녹여야 하기 때문에 wq2를 wq1으로 대체
    sq1 = sq2   #다음 날이 되어 백조가 만날 때까지 움직여야 하기 때문에 sq2를 sq1으로 대체
    wq2 = deque()   #새로운 값을 넣어주기 위해 초기화
    sq2 = deque()   #새로운 값을 넣어주기 위해 초기화
    ans += 1   #날짜 추가
print(ans)

 

https://rebas.kr/780

BOJ 3197 · 백조의 호수

 

대충 이해는 했는데 아직 완벽하진 않아서 더 보고 곱씹으며 이해해서 포스팅 추가해야지...