[백준 3197번] 파이썬 - 백조의 호수

백준 3197_백조의 호수

시간 제한 1초, 메모리 제한 256MB

# 조건

• 두 마리의 백조가 호수에서 살고 있었다.
  • 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
• 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
• 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다.
  • 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
• 아래에는 세 가지 예가 있다.

• 백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
• 며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

• 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
• 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다.
• '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

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

# 접근 방법

• bfs를 이용하여 시뮬레이션 돌려주었다.
• 시간 초과를 해결하기 위하여 처음에 로직을 잘 짜야 될 것 같다.
• 내가 풀이한 로직
  • 백조와 물을 각각 저장할 que와 다음 위치를 저장할 que 총 4개를 만들고
  • 얼음이 녹는 것을 물이 이동하는 것으로 처리
  • 다음 칸이 빙판이라면 임시 큐에 넣고 위치 저장
  • 이후 백조가 최대 갈 수 있는 거리까지 이동 시키며 마찬가지로 다음 칸이 빙판이면 임시 큐에 넣는다.
  • 백조가 못 만난다면 물과 백조에 대한 que를 임시 큐로 복사해주고 임시 큐를 초기화 해준다.
• 위의 과정 반복
• pypy로만 통과가 된다.
• 다른 분들 코드보고 python으로도 풀어보기!

from sys import stdin  
from collections import deque  

input = stdin.readline  

dx = [-1,1,0,0]  
dy = [0,0,-1,1]  
ICE = 2  
SWAN = 1  
WATER = 0  

r,c = map(int, input().split())  
board = []  
visited = [[False] * c for _ in range(r)]  
ice_visited = [[0] * c for _ in range(r)]  
visited_num = 1  

edges = deque()  
swan = []  

for x in range(r):  
    board.append(list(input().strip()))  
    for y in range(c):  
        if board[x][y] == '.':  
            board[x][y] = WATER  
        elif board[x][y] == 'L':  
            swan = (x,y)  
            board[x][y] = SWAN  
        else:  
            board[x][y] = ICE  

def solv():  
    global visited, visited_num  
    ans = 0  
    set_edges()  
    visited[swan[0]][swan[1]] = True  
    swan_q = deque([swan])  
    while True:  
        visited_num += 1  
        swan_q = swan_bfs(swan_q)  
        if not swan_q:  
            print(ans)  
            break  
        melt_ice()  
        ans += 1  

def melt_ice():  
    global edges,ice_visited,remove_visited  

    edges_cnt = len(edges)  
    for _ in range(edges_cnt):  
        x,y = edges.pop()  
        board[x][y] = WATER  
        for d in range(4):  
            nx = x + dx[d]  
            ny = y + dy[d]  

            if point_validator(nx, ny):  
                if board[nx][ny] == ICE and ice_visited[nx][ny] == 0:  
                    edges.appendleft((nx,ny))  
                    ice_visited[nx][ny] = visited_num  

def swan_bfs(swan_q):  
    global visited  

    nxt_q = deque()  
    while swan_q:  
        x,y = swan_q.pop()  

        for d in range(4):  
            nx = x + dx[d]  
            ny = y + dy[d]  

            if point_validator(nx,ny) and not visited[nx][ny]:  
                visited[nx][ny] = True  
                if board[nx][ny] == SWAN:  
                    return None  
                elif board[nx][ny] == ICE:  
                    nxt_q.appendleft((nx,ny))  
                else:  
                    swan_q.appendleft((nx,ny))  
    return nxt_q  
def set_edges():  
    for x in range(r):  
        for y in range(c):  
            if board[x][y] == ICE:  
                for d in range(4):  
                    nx = x + dx[d]  
                    ny = y + dy[d]  

                    if point_validator(nx, ny) and board[nx][ny] in [WATER, SWAN]:  
                        ice_visited[x][y] = visited_num  
                        edges.appendleft((x, y))  
                        break  

def point_validator(x,y):  
    if x < 0 or y < 0 or x >= r or y >= c:  
        return False  
    return True  
solv()