두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 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..... ................. 처음 첫째 날 둘째 날
- 하루가 지날때마다 사면 중 하나라도 물과 닿아있는 얼음은 녹음
- 녹아서 길이 생김 -> 백조 만날 수 있나?
- 못 만나면 다시 반복
- 하루마다 얼음 녹는 것 => BFS
- 백조 만나는 것 => BFS
문제 자체 난이도보다 시간 초과를 잡는 게 너무 어려웠다
첫번째 코드
import sys
from collections import deque
N,M = map(int, sys.stdin.readline().split())
dx = [-1,1,0,0] #상하좌우
dy = [0,0,-1,1]
waterdq = deque()
spq = deque([])
arr = []
spawn = []
ans = 1
def spawnq():
visited = [[False for _ in range(M)] for _ in range(N)]
next_dq = deque([])
while spq:
x,y = spq.popleft()
visited[x][y] = True
if x == spawn[1][0] and y == spawn[1][1]:
return True, None
else:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and ny >= 0 and nx < N and ny < M and visited[nx][ny] == False:
visited[nx][ny] = True
if arr[nx][ny] == '.':
spq.append((nx,ny))
else:
next_dq.append((nx,ny))
return False, next_dq
def waterq():
visited = [[False for _ in range(M)] for _ in range(N)]
new_water = deque([])
while waterdq:
x,y = waterdq.popleft()
visited[x][y] = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and ny >= 0 and nx < N and ny < M and not visited[nx][ny]:
if arr[nx][ny] == 'X':
arr[nx][ny] = '.'
new_water.append((nx,ny))
return new_water
for i in range(N):
k = sys.stdin.readline().split()
tmp = []
for j in range(len(k[0])):
if k[0][j] == 'L':
tmp.append('.')
spawn.append((i,j))
elif k[0][j] == '.':
waterdq.append((i,j))
tmp.append(k[0][j])
else:
tmp.append(k[0][j])
arr.append(tmp)
spq.append((spawn[0][0],spawn[0][1]))
while True:
new_water = waterq()
waterdq = new_water
res, nxtq = spawnq()
if(res):
print(ans)
break
spq = nxtq
ans += 1
허허.. 처참한 결과물
포기할까 하다가 오기가 생겨서 계속 해봤는데
고친 코드
import sys
from collections import deque
sys.stdin = open('./input.txt', 'r')
N,M = map(int, sys.stdin.readline().split())
dx = [-1,1,0,0] #상하좌우
dy = [0,0,-1,1]
def spawnq(arr,visited, spq):
next_dq = deque() #얼음으로 막힌 부분에 대한 큐(다음에 돌릴 큐)
while spq:
x,y = spq.popleft()
if x == spawn[1][0] and y == spawn[1][1]: #두번쨰 백조의 위치에 오면 리턴
return True, 0
for i in range(4):
nx = x + dx[i] #상하죄우
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == False:
visited[nx][ny] = True
if arr[nx][ny] == 'X': #얼음을 만났다면
next_dq.append((nx,ny)) #next_dq에 넣어줌
else:
spq.append((nx,ny)) #물이라면 기존 큐에 넣어줌(더 나아갈 수 있음)
return False, next_dq #다음에 돌릴 큐 리턴
def waterq(waterdq, arr):
new_water = deque() #얼음이 물로 바뀐 위치 큐 (다음에 돌릴 큐)
while waterdq:
x,y = waterdq.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 'X': #현재 위치(물)에서 상하좌우를 했을때 얼음을 만난다면
arr[nx][ny] = '.' #얼음을 물로 바꿔주고
new_water.append((nx,ny)) #새롭게 생겨난 부분이니까 new_water에 넣어줌
return new_water #다음에 돌릴 큐 리턴
waterdq = deque() #물 큐
arr = [] #호수맵
spawn = [] #백조 위치
ans = -1
for c in range(N):
tmp = list(sys.stdin.readline().rstrip())
for i,v in enumerate(tmp):
if v == 'L' or v=='.': #백조이거나 물이면 물 큐에 넣어줌
waterdq.append((c,i))
if v == 'L':
spawn.append((c,i)) #백조라면 그 위치를 백조 리스트에 넣어줌
arr.append(tmp)
spq = deque() #백조 큐(얼음에 막힌 위치가 들어옴)
spq.append((spawn[0][0], spawn[0][1])) #첫번째 백조 위치 넣어줌
visited = [[False for _ in range(M)] for _ in range(N)] #방문 여부 확인 리스트
visited[spawn[0][0]][spawn[0][1]] = True #첫번째 백조 위치 방문 True
while True:
ans += 1 #하루가 지남
res, nxtq = spawnq(arr,visited, spq)
if(res):
print(ans)
break
waterdq= waterq(waterdq, arr)
spq = nxtq
point
<백조 bfs>
- 백조가 만나는 것을 전역 visited 배열로 계속 업데이트 해줘야 시간 효율성이 좋음
- 큐를 백조 위치부터 계속 돌리는게 아니라, 막힌 부분(얼음)을 만나면 새로운 큐에 모아서 기존 큐를 업데이트 해줌(중복 없이 막힌 부분에 대해서만 bfs 진행)
<물 bfs>
- 물에 해당하는 부분만 큐에 담아서 그 주변의 얼음만 녹이기 때문에 visited배열 필요 없음 => append할 필요 없음
- 물 또한 얼음이 새롭게 물로 변하는 위치를 큐에 담아 기존 큐를 업데이트 해줌(새로운 물 위치에 대해서만 주변 얼음을 녹이면 됨 => 시간 효율성)
즉 새로 생겨나는 부분만 큐에 담아 돌리면 됨 !!
주석 참고 !!
