백준 2842 파이썬 문제풀이

문제

상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.

매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.

상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌다. 상덕이가 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자. 이때, 가장 작은 피로도로 모든 집에 배달을 하려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)

다음 N개 줄에는 마을을 나타내는 행렬이 주어진다. 'P'는 한 번만 주어지며, 'K'는 적어도 한 번 주어진다.

다음 N개 줄에는 행렬로 나뉘어진 지역의 고도가 행렬 형태로 주어진다. 고도는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 가장 작은 피로도를 출력한다.

문제풀이

나는 이 문제를 두 포인터 + BFS로 풀었으며, 시간복잡도는 O(m * N^2)으로 예상한다. m은 기입된 수의 갯수인데, 결국 최악의 경우 N^2개가 될 것이므로 O(N^4)이 될 것이다. 단, N의 값이 50으로 N^4은 625만으로 큰 문제 없이 시간 안에 풀 수 있었다.

 

먼저 BFS를 어떻게 구현할지를 생각해본다. BFS를 구현할 때, 어떤 순서로 배달을 했는지, 현재 배달한 소포의 갯수가 몇개인지는 전혀 중요하지 않다. 중요한 것은 특정 조건 내에서 특정 지점을 다 방문했는지를 판별하는 것이다. 따라서, 방문 체크 배열을 만들 때는 진행된 시간만 기록해서 여기에 방문했는지를 판별할 수 있도록만 해준다. 

위의 상태처럼 해당 위치에 몇번을 방문했는지는 전혀 필요가 없다. 그 지역에 현재 내가 가지고 있는 조건으로 방문할 수 있는지, 없는지만 판별을 하면 된다.  따라서 BFS를 짜는 논리는 다음과 같다.

1. P 지점에서 0초로 시작한다.
2. 가고자 하는 지점이 현재 조건을 만족한다면(최소값 < 다음 지점 < 최대값), 1초를 추가해서 해당 지역을 방문처리하고, 큐에 넣어준다.
3. 큐가 있는 동안 2를 반복한다. 

BFS를 구현했다면, 이제 경계 조건을 정하는 방법을 확인한다. 처음에는 두 포인터 + 이분 탐색으로 진행을 하고자 했다. 왼쪽 경계 조건을 이분 탐색으로 구한 후, 오른쪽 경계 조건을 이분 탐색으로 구하는 방식이었다. 이 경우 큰 논리적 헛점이 존재했는데  왼쪽, 오른쪽의 경계 조건은 서로가 가지는 값에 독립적이지 못하기 때문에 그렇게 접근할 경우 오답처리가 된다.

 

따라서, 두 포인터를 활용해 좌, 우측의 경계 조건을 한꺼번에 고려하는 방식으로 접근해야한다. 좌, 우측의 경계 조건을 한번에 고려하기 위해서 시작하는 지점을 동일하게 지정했다. 지정한 후, 현재 조건에서 BFS가 불가능하다면 우측 경계 조건을 조금씩 키운다. 현재 조건에서 BFS가 가능하다면 좌측 경계 조건을 키워서 BFS를 만족하는지 확인한다. BFS를 반복할 때마다, BFS가 정상적으로 완료된다면 현재 상태의 경계 조건의 최소값을 업데이트 해준다.

코드는 아래와 같다.

import sys
from collections import deque


def bfs(my_list,dr,dc,n,lv,rv, stack) :

    #변수 선언
    que = deque()

    v = [[9876543210 for _ in range(n)] for _ in range(n)]


    if lv <= my_list[dr][dc] <= rv :
        que.append((dr, dc, 0))
        v[dr][dc] = 0


    while que :
        r,c, cnt = que.popleft()
        next_cnt = cnt + 1


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

            if -1< next_r < n and -1 < next_c< n :
                if  lv <= my_list[next_r][next_c] <= rv:
                    if v[next_r][next_c] > next_cnt :
                        v[next_r][next_c] = next_cnt
                        que.append((next_r, next_c, next_cnt))

    for r,c in stack :
        if v[r][c] == 9876543210 :
            return False

    return True



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

def find_start(a,n) :
    for i in range(n) :
        for j in range(n) :
            if a[i][j] == 'P' :
                return (i,j)

def find_k(a,n) :
    stack = []
    for i in range(n) :
        for j in range(n) :
            if a[i][j] == 'K' :
                stack.append((i,j))
    return stack




n = int(sys.stdin.readline().rstrip())
a = []
for _ in range(n) :
    a.append(str(sys.stdin.readline().rstrip()))

des = find_start(a,n)
k_posi = find_k(a,n)



my_list = []
num_list = []
for _ in range(n) :
    temp = list(map(int,sys.stdin.readline().split()))
    my_list.append(temp)
    for c in temp :
        num_list.append(c)

num_list = sorted(num_list)

lidx,ridx = 0,0
answer = 9876543210

while lidx <= len(num_list) - 1 and ridx <= len(num_list) - 1  :

    lv = num_list[lidx]
    rv = num_list[ridx]

    if ridx == len(num_list) - 1 :
        ff =  bfs(my_list,des[0],des[1],n, lv, rv, k_posi)

        if ff == True :
            lidx +=1
            answer = min(answer, rv - lv)
        else :
            break


    else :
        ff =  bfs(my_list,des[0],des[1],n, lv , rv , k_posi)

        if ff == True :
            lidx +=1
            answer = min(answer, rv-lv)
        else :
            ridx += 1

print(answer)