백준 #3197 백조의 호수 (파이썬)

Yongjun Park·2022년 6월 1일
BFSpython백준
1

문제집: 단기간 성장

목록 보기
4/19

오늘의 한 마디
완전히 똑같은 맵에서 BFS를 여러번 해야 한다면... 이전에 했던 정보를 버리지 마라!

언뜻 짜면서 컴퓨터가 같은 짓을 여러번 할 것이라는 생각이 든다면, 반드시 시간 초과가 나는 알고리즘이다.

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 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'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

예제 입력 1

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

예제 출력 1

3

예제 입력 2

4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

예제 출력 2

2

예제 입력 3

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

예제 출력 3

2

발상

Try #1 : 매일매일 초기화해서 BFS 돌리기

알고리즘 분류에는 분리 집합(=Union Find) 이 있었는데,
도대체 어디서 어떻게 Union Find를 사용해야 할지 감이 안 와서 포기했다.

문제만 읽으면 BFS로도 충분히 구현해낼 수 있을 거라 생각해서 그냥 문제에서 말한 대로 짜봤다.

__main__ 함수는 다음과 같다. 

day = 0

while True:
    if can_meet():
        break
    melt_ice()
    day += 1

print(day)

can_meet 함수는 다음과 같다. 

def can_meet():
    visited = [[False]*C for _ in range(R)]
    q = [(swan_y, swan_x)]
    while q:
        y, x = q.pop()
        if (y, x) == (target_swan_y, target_swan_x):
            return True
        for dy, dx in DIRS:
            if not (0 <= y+dy < R and 0 <= x+dx < C):
                continue
            if visited[y+dy][x+dx]:
                continue
            if lake[y+dy][x+dx] == 'X':
                continue
            visited[y+dy][x+dx] = True
            q.append((y+dy, x+dx))
    return False

매번 시작점은 (swan_y, swan_x)이다.
즉, 매번 같은 점에서 시작해서 BFS를 해 나간다.

만들 당시, 이 과정이 약간 비효율적인 것 같다는 생각은 있었지만 어떻게 개선해야 할지 몰라서 그냥 짰다.

melt_ice 함수는 다음과 같다. 

def melt_ice():
    del_list = []
    for idx, (y, x) in enumerate(ices):
        for dy, dx in DIRS:
            if not (0 <= y+dy < R and 0 <= x+dx < C):
                continue
            if lake[y+dy][x+dx] == '.':
                lake[y][x] = ',' # 임시
                del_list.append(idx)
                break

    for idx in del_list[::-1]:
        y, x = ices[idx]
        lake[y][x] = '.'
        del ices[idx]

처음에는 lake의 모든 (y, x) 점에 대하여 이중 for문을 돌린 채로 dy, dx로 삼중 for문을 돌리는 방식으로 짰었는데, (뭐.. 지나고 나서 생각해보면 이건 O(n^3)은 아니다. O(4n^2)일 것이다.) 그것보다는 X, 즉 빙하의 좌표들을 미리 저장해놓고 그 리스트에 대해서만 체크하면 조금 더 빠르게 돌아가겠다 생각해서 그렇게 바꿨다.

그런데 이건 시간 복잡도를 개선했다기 보다는 자잘한 코드 튜닝 정도의 성과밖에 주지 않았다. 

import sys
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

R, C = map(int, sys.stdin.readline().rstrip().split())
lake = []
for _ in range(R):
    lake.append(list(sys.stdin.readline().rstrip()))

def find_swan():
    swan_y, swan_x = -1, -1
    target_swan_y, target_swan_x = -1, -1
    for i in range(R):
        for j in range(C):
            if lake[i][j] == 'L':
                if (swan_y, swan_x) == (-1, -1):
                    swan_y, swan_x = i, j
                else:
                    target_swan_y, target_swan_x = i, j
                    return swan_y, swan_x, target_swan_y, target_swan_x

swan_y, swan_x, target_swan_y, target_swan_x = find_swan()

def find_ices():
    ices = []
    for i in range(R):
        for j in range(C):
            if lake[i][j] == 'X':
                ices.append((i, j))
    return ices

ices = find_ices()
    
def can_meet():
    visited = [[False]*C for _ in range(R)]
    q = [(swan_y, swan_x)]
    while q:
        y, x = q.pop()
        if (y, x) == (target_swan_y, target_swan_x):
            return True
        for dy, dx in DIRS:
            if not (0 <= y+dy < R and 0 <= x+dx < C):
                continue
            if visited[y+dy][x+dx]:
                continue
            if lake[y+dy][x+dx] == 'X':
                continue
            visited[y+dy][x+dx] = True
            q.append((y+dy, x+dx))
    return False

def melt_ice():
    del_list = []
    for idx, (y, x) in enumerate(ices):
        for dy, dx in DIRS:
            if not (0 <= y+dy < R and 0 <= x+dx < C):
                continue
            if lake[y+dy][x+dx] == '.':
                lake[y][x] = ',' # 임시
                del_list.append(idx)
                break

    for idx in del_list[::-1]:
        y, x = ices[idx]
        lake[y][x] = '.'
        del ices[idx]

day = 0
while True:
    if can_meet():
        break
    melt_ice()
    day += 1

print(day)

예제는 정상적으로 출력했지만,
이렇게 짠 코드는 당연히 시간 초과였다.

Try #2 : 한번 BFS 했던 점을 다시 할 필요가 있을까?

고민하던 중, 질문 탭에서 좋은 힌트를 하나 읽었다.

전문은 위의 링크에 들어가서 읽기로 하고, 핵심적인 내용은 다음과 같다.

프로그램 전체를 통틀어 얼음을 녹이는 함수의 BFS와 백조가 만나는지 확인하는 함수의 BFS가 각각 한번만 진행되어야 합니다. 다음 날에 탐색할 노드를 버퍼 큐에 넣고 다음 날이 되면 버퍼 큐를 큐에 복사해 보세요.

한번만? 어떻게 BFS를 한번만 할 수 있다는 말인가?
버퍼 큐를 도대체 어떻게 구현하라는 말인가?

해설을 읽고서야 그 말의 참뜻을 이해할 수 있었다.

queue : 백조가 다른 백조를 찾을 때 사용하는 queue
next_queue : 백조가 X를 만나면 추후에 물을 녹인 후 확인 할 queue
water : 물의 좌표를 담는 queue, 상하좌우에 X가 있는지 확인해야함
next_water : 빙판을 녹여서 물로 만든 좌표를 다음 주기 때 다시 상하좌우에 X가 있는지 체크해야하므로, 그 정보를 담은 queue

정리하자면,

  • can_meet을 하다가 백조가 만난 X는, 다음번 can_meet에서 반드시 확인해야 한다.
    • 백조는 물 위를 이동할 수 있는데, 어떤 X와 인접할 수 있다면 그 X는 .과 인접해 있는 것이므로, 반드시 돌아오는 melt_ice에서 녹는다.
  • 가장 최근에 melt_ice 수행 중에 녹은 X는, 다음번 melt_ice에 지장을 주는 유일한 .이 된다. 
def can_meet():
	(중략)
            if lake[y+dy][x+dx] == 'X':
                next_queue.append((y+dy, x+dx))
                continue
def melt_ice():
	(중략)
            if lake[y+dy][x+dx] == 'X':
                next_water.append((y+dy, x+dx))
                lake[y+dy][x+dx] = '.'

아직도 이해가 안된다면, 코드를 읽다보면 이해할 수 있을 것이다. 

import sys
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
Y, X = 0, 1

R, C = map(int, sys.stdin.readline().rstrip().split())
swan = []
water = []
lake = []
for y in range(R):
    lake.append(list(sys.stdin.readline().rstrip()))
    for x in range(C):
        if lake[y][x] == 'L':
            swan.append((y, x))
            lake[y][x] = '.'
        if lake[y][x] == '.':
            water.append((y, x))

visited = [[False]*C for _ in range(R)]
swan_q = [swan[0]] # (y, x)
visited[swan[0][Y]][swan[0][X]] = True

def can_meet():
    global visited
    global swan_q
    
    q = swan_q[:]
    swan_q = []
    while q:
        y, x = q.pop()
        if (y, x) == swan[1]:
            return True
        for dy, dx in DIRS:
            if not (0 <= y+dy < R and 0 <= x+dx < C):
                continue
            if visited[y+dy][x+dx]:
                continue
            if lake[y+dy][x+dx] == 'X':
                swan_q.append((y+dy, x+dx)) # 다음 번엔 백조가 반드시 여길 갈 수 있으니까!
                continue
            visited[y+dy][x+dx] = True
            q.append((y+dy, x+dx))
    return False

def melt_ice():
    global water
    
    q = water[:]
    water = []
    while q:
        y, x = q.pop()
        for dy, dx in DIRS:
            if not (0 <= y+dy < R and 0 <= x+dx < C):
                continue
            if lake[y+dy][x+dx] == 'X':
                water.append((y+dy, x+dx)) # 이번에 처음 녹는 빙하에 의해서만 다음번에 녹는 빙하가 생긴다. 
                lake[y+dy][x+dx] = '.'            

day = 0
while True:
    if can_meet():
        break
    melt_ice()
    day += 1
print(day)

위의 글에서 BFS를 한번만 하라는 말은, 진짜 한번만 하라는 게 아니라, 이전에 검사했던 것에 이어서 BFS를 진행함으로써 결과적으로 전체 요소에 대해서 한번씩만 검사한다는 뜻이다.

예제 입출력도 정상적으로 나왔으나, 메모리 초과였다.

왜?

BFS에서 메모리 초과가 되는 경우는 대개, 중복되는 요소가 여러번 들어가는 것이 요인이다.

체크해본 결과, swan_q에 중복되는 요소가 들어갔다.

def can_meet():
	(중략)
            if lake[y+dy][x+dx] == 'X':
                swan_q.append((y+dy, x+dx))
                continue

위를 아래로 수정했다. 

def can_meet():
	(중략)
            if lake[y+dy][x+dx] == 'X':
                visited[y+dy][x+dx] = True
                swan_q.append((y+dy, x+dx))
                continue

미리 visited를 체크해줘야 swan_q에 기존 발생하던 중복이 없어진다.

그리고 (y, x) == swan[1]을 체크하는 조건은 최상단에 위치해 있어 visited 여부에 영향을 받지 않기 때문에 괜찮다.

풀이

import sys
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
Y, X = 0, 1

R, C = map(int, sys.stdin.readline().rstrip().split())
swan = []
water = []
lake = []
for y in range(R):
    lake.append(list(sys.stdin.readline().rstrip()))
    for x in range(C):
        if lake[y][x] == 'L':
            swan.append((y, x))
            lake[y][x] = '.'
        if lake[y][x] == '.':
            water.append((y, x))

visited = [[False]*C for _ in range(R)]
swan_q = [swan[0]] # (y, x)
visited[swan[0][Y]][swan[0][X]] = True

def can_meet():
    global visited
    global swan_q
    
    q = swan_q[:]
    swan_q = []
    while q:
        y, x = q.pop()
        if (y, x) == swan[1]:
            return True
        for dy, dx in DIRS:
            if not (0 <= y+dy < R and 0 <= x+dx < C):
                continue
            if visited[y+dy][x+dx]:
                continue
            if lake[y+dy][x+dx] == 'X':
                visited[y+dy][x+dx] = True # 미리 없애야 swan_q 중복 없어짐. 그리고 (y, x) == swan[1]은 visited된 것에 대해서도 선행 검사하는거라 ㄱㅊ
                swan_q.append((y+dy, x+dx)) # 다음 번엔 백조가 반드시 여길 갈 수 있으니까!
                continue
            visited[y+dy][x+dx] = True
            q.append((y+dy, x+dx))
    return False

def melt_ice():
    global water
    
    q = water[:]
    water = []
    while q:
        y, x = q.pop()
        for dy, dx in DIRS:
            if not (0 <= y+dy < R and 0 <= x+dx < C):
                continue
            if lake[y+dy][x+dx] == 'X':
                water.append((y+dy, x+dx)) # 이번에 처음 녹는 빙하에 의해서만 다음번에 녹는 빙하가 생긴다. 
                lake[y+dy][x+dx] = '.'            

day = 0
while True:
    if can_meet():
        break
    melt_ice()
    day += 1
print(day)

왜 이번 문제만 BFS를 이어서 해야 문제를 풀 수 있었던 거지?

생각해보면, 이제까지 풀었던 BFS 문제들을 살펴보면 완전히 똑같은 맵에서 다시 BFS를 돌렸던 적은 없었다.

  • BFS로 최단거리를 찾는 문제는, 결과적으로 BFS를 한번만 하는 문제다.
  • 아기상어 문제는, 그때그때 최적의 물고기를 하나씩 먹어가면서 상어의 위치 자체가 바뀌기 때문에 매번 BFS를 새로운 맵에서 돌리는 격이 된다.
profile
Yongjun Park
추상화되었던 기술을 밑단까지 이해했을 때의 쾌감을 잊지 못합니다
이전 포스트

백준 #1655 가운데를 말해요 (파이썬)

다음 포스트

백준 #11401 이항 계수 3 (파이썬) : 페르마의 소정리

1개의 댓글

comment-user-thumbnail
Konseo
2023년 9월 18일

이해가 잘 되었습니다 !

답글 달기