⭐⭐⭐⭐[백준] [파이썬] [BFS] [구현] 3197번: 백조의 호수

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

3197번: 백조의 호수 문제 보러가기

 

 

문제

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

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

출력

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

 

예제 입력 

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

 

예제 출력

2

 

---

풀이 설명 

 

문제를 보면 2개의 함수를 만들면 된다는 것을 알수 있다. 

1. 매턴 물 주변의 상하좌우를 살피고 얼음이 있으면 얼음을 녹인다.

2. 백조 2마리가 연결될 수 있는 지 확인하고 연결되면 그만둔다.

1, 2를 반복한다. 

 

2번의 경우 평소 BFS로 풀면 되겠구나 생각했고 

1번의 경우 한턴에 얼음 X를 .으로 바꿔버리면 그걸 물이라고 생각해서 그 옆 얼음도 녹여버릴 수 있게 매턴 업데이트 하는 식이겠구나 생각하였지만 

틀렸다. 테스트케이스는 다 맞는데... ㅠ

 

1번 얼음의 경우 물의 위치가 모두 담겨 있는 큐에 하나씩 위치를 꺼내보며 얼음이 발견되면 다음 턴 큐에 넣어준다. 

그래야 매턴 완전탐색을 할 필요 없다.

2번의 경우 얼음이 녹고 매턴마나 처음 시작위치에서부터 BFS를 하면 시간초과가 일어난다. 매턴 마다 위치를 저장하고 업데이트 해주어야 한다. 

 

즉,

 

큐를 4개 사용하여야 한다. 

백조가 움직이는 큐, 얼음을 녹이는 큐, 다음턴 백조가 움직여야하는 큐, 다음턴 얼음을 녹이는 큐 

 

나의 틀린 코드 

'''
1. 매 턴마다 얼음을 녹인다.
2. L부터 다른 L까지 만날 수 있는지 확인 한다. 

'''

import sys
import copy
from collections import deque
sys.stdin=open('input.txt', 'r')
input = sys.stdin.readline
dxs=[1,0,0,-1]
dys=[0,1,-1,0]

def in_range(nx,ny):
    return 0<=nx<R and 0<=ny<C

def melt():
    next_board = copy.deepcopy(board)
    for i in range(R):                          # 매턴마다 완전탐색을 해야한다. -> 시간초과 발생
        for j in range(C):
            if board[i][j]=='X':
                for dx,dy in zip(dxs,dys):
                    nx=i+dx
                    ny=j+dy
                    if in_range(nx,ny) and board[nx][ny]=='.':
                        next_board[i][j]='.'
                        break
    
    return next_board
    
def BFS():                  # 매턴마다 똑같은 위치에서 BFS를 수행하면 시간초과 발생 
    Q = deque()
    Q.append(start)
    visited = [[0]*C for _ in range(R)]
    while Q:
        x,y=Q.popleft()
        visited[x][y]=1
        if x==target[0] and y==target[1]:
            return True 
        
        for dx,dy in zip(dxs,dys):
            nx=x+dx
            ny=y+dy
            if in_range(nx,ny) and board[nx][ny]!='X' and visited[nx][ny]==0:
                visited[nx][ny]=1
                Q.append((nx,ny))
        
        
    return False

if __name__=="__main__":
    R,C = map(int, input().split())

    birds = []
    board = []
    for i in range(R):
        row = list(input().strip())
        board.append(row)
        for j in range(C):
            if board[i][j]=='L':
                birds.append([i, j])
    
    start = birds[0]
    target = birds[1]
    board[start[0]][start[1]], board[target[0]][target[1]] = '.', '.'
    
    cnt = 0
    while True:
        if BFS() is True:
            break
        
        else:
            board = melt()
            cnt+=1
        
        
        
    print(cnt)

 

정답 코드 

from collections import deque
import sys
sys.stdin=open('input.txt', 'r')

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def in_range(nx,ny):
    return 0<=nx<R and 0<=ny<C

def bfs():      # SQ와 SQ_temp를 분리해서 생각하지 않으면 시간초과 발생
    while SQ:
        x, y = SQ.popleft()
        if x == x2 and y == y2:
            return True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if in_range(nx,ny) and swanCheck[nx][ny]==0:
                if board[nx][ny] == '.':
                    SQ.append([nx, ny])
                else:
                    SQ_temp.append([nx, ny])    # 막혀있는 얼음 위치가 다음턴에 녹아있고 거기서부터 생각해서 시작하면 된다.
                swanCheck[nx][ny] = 1
    return False

def melt():
    while WQ:
        x, y = WQ.popleft()
        if board[x][y] == 'X':              # 다음턴에 녹이기 위해 
            board[x][y] = '.'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if in_range(nx,ny) and waterVisited[nx][ny]==0:

                if board[nx][ny] == 'X':        # 얼음이 있는 위치만 따로 찾아서 
                    WQ_temp.append([nx, ny])    # 다음턴에 녹이기 
                else:
                    WQ.append([nx, ny])   # 한턴 별로 얼음을 녹이기 위해 분리해서 생각해줘야함
                    
                waterVisited[nx][ny] = 1


if __name__=="__main__":
    
    R, C = map(int, input().split())
    swanCheck = [[0]*C for _ in range(R)]
    waterVisited = [[0]*C for _ in range(R)]

    board, swan = [], []
    
    SQ, WQ = deque(), deque()
    SQ_temp, WQ_temp = deque(), deque()
    
    for i in range(R):
        row = list(input().strip())
        board.append(row)
        for j in range(C):
            if board[i][j] == 'L':      # 백조가 있는 위치 
                swan.extend([i, j])     # 2개의 백조 위치 
                WQ.append([i, j])       # 백조가 있는 위치도 물
            elif board[i][j] == '.':    # 물이 있는 위치 
                waterVisited[i][j] = 1
                WQ.append([i, j])       # 물과 닿는 얼음 X를 상하좌우 살핌 

    x1, y1, x2, y2 = swan           # 2개의 백조 위치 
    SQ.append([x1, y1])             # 1개 백조 위치를 기준 
    board[x1][y1], board[x2][y2], swanCheck[x1][y1] = '.', '.', 1   # 백조가 있던 자리는 물로 대체
    cnt = 0

    while True:
        melt()      # 현재 물의 위치들에서 상하좌우에 X(얼음)이 있는지 확인하고 녹이기
        if bfs():
            print(cnt)
            break
        SQ, WQ = SQ_temp, WQ_temp       # 새롭게 물이된곳과 백조위치 업데이트 
        SQ_temp, WQ_temp = deque(), deque() 
        cnt += 1
        # 얼음 녹이는 것을 한턴별로 생각하기 위해 WQ와 WQ_temp를 분리해서 구현 
        # swanCheck와 함께 매턴 별로 두 백조의 시작위치부터 탐색하는것이 아니라 
        # 매턴 별로 이전 위치를 기억하면서 수행하기 위해 SQ와 SQ_temp를 분리해서 생각