문제 바로가기
문제:
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다. 며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
입력:
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
출력:
첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
풀이:
아이디어는 예전에 풀었던 치즈와 똑같다.
bfs한번 진행할때마다 x들을 한칸씩 지워준다.
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split(" "))
lst = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
index_L = []
for x in range(len(lst)):
for y in range(len(lst[0])):
if lst[x][y] == "L":
index_L.append((x, y))
start = index_L[0]
end = index_L[1]
def meet_swan(start, end):
visited = [[False] * m for _ in range(n)]
Q = deque()
Q.append(start)
visited[start[0]][start[1]] = True
while Q:
x, y = Q.popleft()
for dx, dy in move:
nx = dx + x
ny = dy + +y
if nx == end[0] and ny == end[1]:
return True
if 0 <= nx < n and 0 <= ny < m and lst[nx][ny] != "X" and not visited[nx][ny]:
visited[nx][ny] = True
Q.append((nx, ny))
def water_melt():
visited = [[False] * m for _ in range(n)]
next_Q = deque()
for r in range(n):
for c in range(m):
if lst[r][c] == '.' and not visited[r][c]:
Q = deque([(r, c)])
visited[r][c] = True
while Q:
x, y = Q.popleft()
for dx, dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
visited[nx][ny] = True
if lst[nx][ny] == ".":
Q.append((nx, ny))
elif lst[nx][ny] == "X":
next_Q.append((nx, ny))
for x, y in next_Q:
lst[x][y] = "."
res = 0
while True:
if meet_swan(start, end) == True: # 만나면
break # 종료
water_melt() # 안 만나면 한 번 녹여줌
res += 1
print(res)
첫 코드는 이렇게 짰다.
하지만 bfs랑, meet_swan을할때
매번 visited 를 만들어줘서 시간초과가 난다.
즉 visited를 들고 다니면 괜찮다는 생각을 해서. water_melt에서 visited를 global로 했더니
무한루프가 돌고 해결이 되지않았다.
해결.
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m = map(int, sys.stdin.readline().split(" "))
lst = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
index_L = []
water = deque()
for x in range(len(lst)):
for y in range(len(lst[0])):
if lst[x][y] == "L":
index_L.append((x, y))
if lst[x][y] == "L" or lst[x][y] == ".":
water.append((x,y))
start = index_L[0]
end = index_L[1]
Q = deque([(start[0],start[1])])
visited = [[False] * m for _ in range(n)]
count = 0
# 백조가 갈 수 있는 위치들 next_Q에 담김
def find_swan(lst, visited, Q):
next_Q = deque()
while Q:
x, y = Q.popleft()
if x == end[0] and y == end[1]:
return True, []
for dx, dy in move:
nx = dx + x
ny = dy + y
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
visited[nx][ny] = True
if lst[nx][ny] == "X":
next_Q.append((nx, ny))
else:
Q.append((nx, ny))
return False, next_Q
def melt_ice(water, lst):
next_water = deque()
while water:
x, y = water.popleft()
for dx,dy in move:
nx = x + dx
ny = y + dy
if not 0 <= ny < m or not 0 <= nx < n:
continue
if lst[nx][ny] == 'X':
next_water.append((nx,ny))
lst[nx][ny] = '.'
return next_water
while True:
flag, Q = find_swan(lst, visited, Q) # 백조가 다음 턴에 설 수 있는 위치 찾기
if flag:
break
water = melt_ice(water, lst)
print(water, Q)
count += 1
print(count)
water라는 리스트에 물을 처음에 다 넣었고.
한번씩 돌때마다. 한칸씩 전진하도록 하여 x를 .으로 바꿔준다.
next_Q 에는 백조가 갈 수 있는 곳을 저장해 둔다.
댓글