문제
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 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'은 백조가 있는 공간으로 나타낸다.
출력
진짜 쉽게 잘 설명해 놓으신 글..!!
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)
대충 이해는 했는데 아직 완벽하진 않아서 더 보고 곱씹으며 이해해서 포스팅 추가해야지...
'Coding > Baekjoon' 카테고리의 다른 글
[백준][파이썬]11401번 - 이항 계수 3 (0) | 2022.05.02 |
---|---|
[백준][파이썬]1655번 - 가운데를 말해요 (0) | 2022.04.29 |
[백준][파이썬]12865번 - 평범한 배낭 (0) | 2022.04.27 |
[백준][파이썬]10870번 (0) | 2021.01.27 |
[백준][파이썬]10872번 (0) | 2021.01.26 |