# 3197번 Fail
import sys
def find(number):
if parents[number] == number:
return number
parents[number] = find(parents[number])
return parents[number]
def merge(root,child):
parents[child] = root
def water_merge():
while water:
cx,cy = water.pop(0)
flag = True
for k in range(4):
nx = cx + dx[k]
ny = cy + dy[k]
if 0<= nx <R and 0<= ny <C:
if check_map[nx][ny] != -1 and check_map[nx][ny] != check_map[cx][cy]:
parentA = find(check_map[cx][cy])
parentB = find(check_map[nx][ny])
if parentA != parentB:
merge(parentA,parentB)
check_map[nx][ny] = parentA
elif check_map[nx][ny] == -1 and flag:
melt_water.append((cx,cy))
flag = False
def water_melt():
while melt_water:
cx,cy = melt_water.pop(0)
root = find(check_map[cx][cy])
for k in range(4):
nx = cx + dx[k]
ny = cy + dy[k]
if 0<= nx <R and 0<= ny <C:
if check_map[nx][ny] == -1:
water.append((nx,ny))
check_map[nx][ny] = root
R,C = map(int,input().split())
arr = [list(sys.stdin.readline()) for _ in range(R)]
check_map = [[-1]*C for _ in range(R)]
parents = [-1]*(R*C)
cnt = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
swan = []
water = []
for x in range(R):
for y in range(C):
if arr[x][y] == '.' or arr[x][y] == 'L':
water.append((x,y))
parents[cnt] = cnt
check_map[x][y] = cnt
cnt += 1
if arr[x][y] == 'L':
swan.append((x,y))
swan1 = swan[0]
swan2 = swan[1]
time = 0
melt_water = []
while water:
water_merge()
if find(check_map[swan1[0]][swan1[1]]) == find(check_map[swan2[0]][swan2[1]]):
result = time
break
water_melt()
time += 1
print(result)처음 시도했던 실패버전이다.
이 방법은 물을 union find로 한 묶음으로 한뒤, 탐색을 해주는 방식으로 했다. 그러나 이 방식의 문제점은 각 time에 대해 전부다 백조가 연결되어있는지 확인해야 하므로, 시간이 초과가 되었다.
import sys
from collections import deque
import time
def isconnent_swan(start,end,standard_time):
global R,C
visited = [[True] * C for _ in range(R)]
stack = deque()
stack.append((start[0],start[1]))
visited[start[0]][start[1]] = False
while stack:
x,y = stack.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx <R and 0<= ny <C:
if melt_time[nx][ny] <= standard_time and visited[nx][ny]:
visited[nx][ny] = False
stack.append((nx,ny))
if nx == end[0] and ny == end[1]:
return True
return False
def find_max_spend_time():
global R,C
while waters:
x,y,time = waters.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx < R and 0<= ny < C:
if melt_time[nx][ny] == -1:
melt_time[nx][ny] = time + 1
waters.append((nx,ny,time+1))
return time
R,C = map(int,input().split())
origins = [list(sys.stdin.readline()) for _ in range(R)]
melt_time = [[-1]*C for _ in range(R)]
waters = deque()
swans = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for x in range(R):
for y in range(C):
if origins[x][y] != 'X':
waters.append((x,y,0))
melt_time[x][y] = 0
if origins[x][y] == 'L':
swans.append((x,y))
max_time = find_max_spend_time()
min_time = 0
result = 0
while min_time <= max_time:
mid_time = (min_time + max_time)//2
if isconnent_swan(swans[0],swans[1],mid_time):
answer = mid_time
max_time = mid_time - 1
else:
min_time = mid_time + 1
print(answer)두번째로 찾은 방법은 빙하가 녹는 시간을 미리 구해주는 것이다. BFS를 통해 각 빙하들이 녹는 시간들을 찾아주고, 이분탐색으로 시간을 줄여가면서 백조들끼리 연결되어있는지 구하는 것이다.
빙하가 녹는시간을 구해놓고, 기준시간보다 작거나 같을시에는 이동이 가능하다고 판별을 해주었다.
하지만 이 방법도 백조가 연결되어있는지 매번 BFS를 해야하므로, 실행시간이 오래걸리는 편이었다.
from collections import deque
import sys
R,C = map(int,input().split())
lake = [list(sys.stdin.readline()) for _ in range(R)]
waters = deque()
swans = []
water_chk = [[True] *C for _ in range(R)]
swan_chk = [[True] *C for _ in range(R)]
for x in range(R):
for y in range(C):
if lake[x][y] != 'X':
waters.append((x,y))
water_chk[x][y] = False
if lake[x][y] == 'L':
swans.append((x,y))
lake[x][y] = '.'
start_swan,end_swan = swans
swans = deque()
swans.append(start_swan)
swan_chk[start_swan[0]][start_swan[1]] = False
times = 0
new_water = deque()
new_swans = deque()
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while True:
while waters:
x,y = waters.popleft()
lake[x][y] = '.'
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx < R and 0<= ny <C:
if lake[nx][ny] == 'X' and water_chk[nx][ny]:
new_water.append((nx,ny))
water_chk[nx][ny] = False
while swans:
x,y = swans.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx <R and 0<=ny<C:
if swan_chk[nx][ny]:
if lake[nx][ny] == '.':
swans.append((nx,ny))
elif lake[nx][ny] == 'X':
new_swans.append((nx,ny))
swan_chk[nx][ny] = False
if not swan_chk[end_swan[0]][end_swan[1]]:
answer = times
break
waters = new_water
swans = new_swans
new_swans = deque()
new_water = deque()
times += 1
print(answer)마지막 방식은 deque를 4개를 써서, 매번 bfs를 처음부터 하지 않아도, 되는 방식으로 해주었다.
water : 현재가 물인 상태인 것들이 모아져있는 deque
new_water : 다음 시간에 녹아질 예정인 빙하들의 deque
swan : 현재 시간에 swan이 돌아다닐수 있는 deque
new_swan : 다음 시간에 swan이 움직일수 있는 deque
이렇게 기능적으로 나눈뒤에,
먼저 water에서 다음에 녹을 water를 찾아준다. 이때 new_water에 들어가는 것은 호수에 빙하인것과 water_chk 한번도 방문하지 않은 곳이여야 한다.
그리고 여기서 처음 water를 pop할때 lake[x][y]를 . 를 입력해주는 것은 이전 time에 우리가 찾아놓은 new_water가 녹았기 때문에, 이때 값을 변경시켜주는 것이다.
이렇게 한뒤에, swan를 bfs를 돌리면서 물인곳은 계속 swan에 추가해서 bfs를 해주고, 만약 빙하인곳은 다음번에 들릴곳이기 때문에 new_swan에 넣어준다.
그리고 빙하와 물 상관없이 swan 방문을 check해준다.
이렇게 작업을 한뒤에, 우리가 찾는 반대편 swan에 도착했는지 확인을 해주고, 그때의 시간을 출력해주면 된다.
도착하지 않았으면, new_water를 water에 넣어주고, new_swan을 swan에 넣어준뒤 초기화를 시켜준다
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 1987 알파벳 (0) | 2021.02.03 |
|---|---|
| [BOJ/백준] 1655 가운데로 말해요 (0) | 2021.02.02 |
| [BOJ/백준] 1309 동물원 (0) | 2021.01.31 |
| [BOJ/백준] 11403 경로찾기 (0) | 2021.01.30 |
| [BOJ/백준] 9251 LCS (0) | 2021.01.29 |
