[BOJ/백준] 백준 3197 백조의 호수 파이썬

문제 링크 : https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

몇번 못풀다가 다시 풀어보고 오늘 드디어 맞았다.

처음 맞았을 때 너무 느려서 다시 풀었지만 그래도 좀 느린거 같다.

처음 풀었을 때 너무 복잡하게 생각했던 것 같다.

좀 단순하게 문제를 볼 필요가 있는듯하다.

 

이전 풀이 알고리즘 및 코드

얼음이 녹을 때 여러 물들이 합쳐지는 것에서 시간이 많이 잡아 먹힌듯 하다.

1.처음 백조의 위치를 저장해둔다 2. 물인 공간에 번호를 매기고 백조정보에 현재 백조가 몇번 물에 있는지 저장하고 얼음 덩어리에 가장자리를 찾아 edges 큐에 저장한다. 3. 반복문 시작   3.1 두 백조가 같은 번호에 있는지 체크     3.1.1 같다면 시간 출력 후 종료   3.2 얼음 녹이기     3.2.1 edges 길이만큼 반복문 시작        3.2.1.1 4방향 탐색          3.2.1.1.1 얼음이고 처음 방문한 얼음이라면 edges에 push          3.2.1.1.2 물이라면 주변 물중 가장 큰 물의 번호 저장        3.2.1.2 물 영역 합치기 시작          3.2.1.2.1 해당 점을 기준으로 물 영역 번호를 수정한다          3.2.1.2.2 만약 백조가 있는 위치라면 해당 백조의 물 번호 수정

 

from sys import stdin
from collections import deque

input = stdin.readline

dx = [-1,1,0,0]
dy = [0,0,-1,1]
ICE = -9


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

l_info = [[]]
edges = deque()
water_size = [0]
for x in range(r):
    board.append(list(input().strip()))
    for y in range(c):
        if board[x][y] == '.':
            board[x][y] = 0
        elif board[x][y] == 'L':
            board[x][y] = 0
            l_info.append([0,x,y])
        else:
            board[x][y] = ICE

def init_board():
    num = 1
    for sx in range(r):
        for sy in range(c):
            if board[sx][sy] == 0:
                init_board_bfs(sx,sy,num)
                num += 1

def init_board_bfs(sx,sy,num):
    global board, edges, ice_visited,visited_num,water_size
    cnt = 1
    q = deque([(sx, sy)])
    board[sx][sy] = num

    while q:
        x,y = q.pop()
        if x == l_info[1][1] and y == l_info[1][2]:
            l_info[1][0] = num
        elif x == l_info[2][1] and y == l_info[2][2]:
            l_info[2][0] = num

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

            if point_validator(nx, ny):
                if board[nx][ny] == 0:
                    board[nx][ny] = num
                    q.appendleft((nx,ny))
                    cnt += 1
                elif board[nx][ny] == ICE and ice_visited[nx][ny] == 0:
                    ice_visited[nx][ny] = visited_num
                    edges.appendleft((nx,ny))
    water_size.append(cnt)
def solv():
    global visited_num
    ans = 0
    init_board()
    while True:
        visited_num += 1
        if l_info[1][0] == l_info[2][0]:
            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()
        remove_visited[x][y] = visited_num
        max_water_size = 0
        water_num = 0

        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
                elif board[nx][ny] > 0:
                    if max_water_size < water_size[board[nx][ny]]:
                        max_water_size = water_size[board[nx][ny]]
                        water_num = board[nx][ny]
        merge_water(x,y,water_num)
def merge_water(sx,sy,target):
    global board,water_size

    q = deque([(sx,sy)])
    board[sx][sy] = target
    while q:
        x,y = q.pop()
        water_size[target] += 1

        if x == l_info[1][1] and y == l_info[1][2]:
            l_info[1][0] = target
        elif x == l_info[2][1] and y == l_info[2][2]:
            l_info[2][0] = target

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

            if point_validator(nx, ny) and board[nx][ny] > 0 and board[nx][ny] != target:
                board[nx][ny] = target
                q.appendleft((nx,ny))

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

solv()

 

너무 느려서 다시 생각해보니 그냥 백조, 얼음 큐 두개 사용해서 각각 이동시키고 녹이면 됐다.

한마리 백조는 가만 있고 다른 백조가 이동하다 찾는 순간 끝내면 된다.

백조를 현재 얼음 상황에서 얼음의 앞까지 이동시키고

얼음을 녹이고 다시 4방향 탐색해서 얼음 큐에 넣는다.

하다가 백조가 있는 곳도 물인데 이것을 체크안해서 틀렸었다.

 

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()