백준 3197 백조의 호수 파이썬

https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

 

​

시간을 줄이는데 피똥 싼 문제다. 처음에 접근한 방법은 내가 생각하기에는 BFS 단 2번에 처리할 수 있다고 생각해서 손쉽게 통과할 줄 알았는데 TLE가 났다. 왜 그런지는.. 나 혼자로는 어려워 백준 게시판에 문의 글을 적어두었다. 혹시나 누군가 답변을 달아주시면 공유를 해보려고 한다.

​

첫번째 접근한 방법은 다음과 같다.

1. 얼음을 깰 수 있는만큼 깬다.
2. 얼음을 깰 수 있는만큼 깬 다음에 백조가 갈 수 있는만큼 이동한다.

​

이렇게 생각한 이유는 다음과 같다.

얼음이 깨지는 곳은 물의 가장자리다. 물의 가장자리와 맞닿는 얼음은 다 깨진다. 그리고 깨진 얼음은 다시 한번 물의 가장자리가 된다. 따라서 마지막에 깨진 얼음을 기억하고, 다음 턴에 동서남북 얼음을 확인하고 깨주면 얼음 배열을 전체를 최소 1번, 최대 4번만 방문해서 다 깰 수 있을 것이라 생각한다.

​

백조가 갈 수 있는 곳도 동일하다. 백조가 갈 수 있는 최대한의 거리는 오늘 기준의 물의 가장자리다. 이 물의 가장자리는 다음 턴에서는 얼음이 깨지는 곳과 맞닿아있다. 따라서 백조는 항상 오늘 갈 수 있는만큼의 가장자리를 기억하면 된다. 얼음이 깨지면 그 다음 턴에서 다시 이동하면 된다. 이 경우 저장되는 백조의 상태가 길어질 것이라고 생각했으나 메모리 / 시간 복잡도를 고려했을 때는 큰 문제가 없다고 생각했다. 왜냐하면 모든 백조는 한번에 하나의 장소만 방문하면 되기 때문이다. 마지막으로 방문한 장소와 맞닿은 곳은 다음 턴에 반드시 물로 바뀌기 때문이다.

​

이렇게 각 열을 최소 2번, 최대 8번만 방문하면 해결될 것으로 예상해서.. 이렇게 해결을 해보려고 했는데... 시간이 무려 10초나 나왔다 ;;;;;

​

​

그래서 하지 않으려고 했던 방법을 사용했다.

1. 먼저 얼음이 깨지는 턴을 배열을 하나 만들어 기록한다.
2. 이분 탐색으로 백조와 백조가 만날 수 있는 날인지를 BFS로 최소값을 구했다.
3. 이분탐색을 한 이유는 예를 들어 10일에 최초로 만날 수 있게 되면 10일 이후로는 항상 만날 수 있기 때문이다. 따라서 10이라는 값을 넣고, 10일이 넘지 않는 한 얼음 배열을 방문하는 식으로 접근했다.

 

 

import sys
from collections import deque
import time

def break_ice(n,m, water,vv):
    global ss1, ss2, rrrrr

    que = deque()
    while water :
        a,b = water.pop()
        que.append((a,b,0))
        vv[a][b] = 0


    while que :
        r,c, day = que.popleft()
        next_day = day + 1

        for rr,cc in tra_list :
            next_r, next_c = r + rr, c + cc

            #경계 만족할 때
            if -1 < next_r < n and -1 < next_c < m:

                # 얼음인 경우에만 집어넣는다.
                if my_list[next_r][next_c] == "X" and vv[next_r][next_c] > next_day:
                    vv[next_r][next_c] = next_day
                    que.append((next_r, next_c, next_day))
                    rrrrr = max(rrrrr, next_day)

    return



def bfs(sr,sc, er, ec, n,m,day):

    que = deque()

    v = [[0 for _ in range(m)] for _ in range(n)]
    que.append((sr,sc))
    v[sr][sc] = 1


    while que :
        r,c = que.popleft()

        if r == er and c == ec:
            return True

        for rr,cc in tra_list :
            next_r, next_c = r + rr, c + cc
            if -1 < next_r < n and -1 < next_c < m:
                if vv[next_r][next_c] <= day and v[next_r][next_c] == 0 :
                    que.append((next_r, next_c))
                    v[next_r][next_c] = day

    return False



tra_list = [[1,0],[0,1],[-1,0],[0,-1]]



water = []
bird = set()
r,c = map(int,sys.stdin.readline().split())
my_list = [[] for _ in range(r)]
for i in range(r) :
    temp = sys.stdin.readline().rstrip()
    for k in temp :
        my_list[i].append(k)
        if k == "." :
            water.append((i,len(my_list[i])-1))
        if k == "L" :
            bird.add((i, len(my_list[i]) - 1))
            water.append((i, len(my_list[i]) - 1))




ans = 1
er,ec = bird.pop()
sr,sc = bird.pop()
v = [[0 for _ in range(c)] for _ in range(r)]
vv = [[5000 for _ in range(c)] for _ in range(r)]


qqq = time.time()

rrrrr = 0
break_ice(r,c,water,vv)
ll = 0

ans = 9876543210
rrrrr += 1
while ll < rrrrr :


    m = (ll+rrrrr) // 2
    if bfs(sr,sc,er,ec,r,c,m) :
        rrrrr = m
        ans = min(ans, m)
    else :
        ll = m + 1

print(ans)