145. 집배원 한상덕

백준

1. bfs, 투포인터

참고

import sys
from collections import deque

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

N = int(input())
board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(N)]

tiredness = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
houses = 0
fatigue = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 'P':
            sx, sy = i, j
        if board[i][j] == 'K':
            houses += 1
        fatigue.append(tiredness[i][j])
# 고도 set 및 정렬 필요 => 정렬 : 투 포인터 set : 중복된 고도 제거
fatigue = sorted(set(fatigue))
left, right = 0, 0
ans = sys.maxsize
while left < len(fatigue):
    visit = [[False] * N for _ in range(N)] # left나 right를 움직일 때마다 visit 초기화 필요
    tired = tiredness[sx][sy] # 시작점 피로도
    q = deque()
    K = 0 # 방문한 집의 개수
    if fatigue[left] <= tired <= fatigue[right]: # 시작점 피로도가 투 포인터 사이의 피로도에 속할 경우에만 BFS시작
        visit[sx][sy] = True
        q.append((sx, sy))
    while q:
        x, y = q.popleft()
        for k in range(8):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < N and 0 <= ny < N:
                if visit[nx][ny]: continue
                tired = tiredness[nx][ny]
                # 현재 피로도가 left, right 사이 피로도일 경우에만 추가로 탐색
                if fatigue[left] <= tired <= fatigue[right]:
                    visit[nx][ny] = True
                    q.append((nx, ny))
                    if board[nx][ny] == 'K': K += 1
    if K == houses: # 집을 모두 방문했을 때
        ans = min(ans, fatigue[right] - fatigue[left]) # 최소 피로도 구하기
        left += 1 # 최소 높이 증가
    elif right + 1 < len(fatigue): # 아직 남아있는 최대 고도가 있을 때
        right += 1 # 최대 고도 증가
    else: break # 집을 모두 방문하지 않았는데 최대 고도일 경우 종료
print(ans)

• fatigue의 변경은 다음과 같다.

  • 참고로, 투포인터는 대부분 정렬된 배열에서만 사용할 수 있다.

#고도 행렬
3 2 4
7 4 2
2 3 1

#고도 리스트
[3, 2, 4, 7, 4, 2, 2, 3, 1]
#중복 제거 및 정렬
[1, 2, 3, 4, 7]

2. C++

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;

int n, h[50][50], dy[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int cnt_k, y_post, x_post; 
char vil[50][51];
vector<int> hhh;

// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴 
int bfs(int low, int high) {
    // to-do
    int cnt = 0;
    bool vt[50][50] = {false, };
    queue<pii> q;
    q.push(pii(y_post, x_post));
    vt[y_post][x_post] = true;
    if (h[y_post][x_post] < low || high < h[y_post][x_post]) return -1;
    while (!q.empty() && cnt < cnt_k) {
        pii cur = q.front();
        q.pop();
        for (int i = 0 ; i < 8 ; i++) {
            int nxty = cur.first + dy[i], nxtx = cur.second + dx[i];
            if (nxty < 0 || n <= nxty || nxtx < 0 || n <= nxtx) continue;
            if (vt[nxty][nxtx]) continue;
            if (h[nxty][nxtx] < low || high < h[nxty][nxtx]) continue;
            if (vil[nxty][nxtx] == 'K') {
                cnt++;
            }
            vt[nxty][nxtx] = true;
            q.push(pii(nxty, nxtx));
        }
    }

    return cnt;
}

// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴 

//int dfs(int low, int high) {
//  // to-do
//}

int main() {
    //freopen("res/B2842.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 0 ; i < n ; i++) {
        scanf("%s", vil[i]);
    }
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < n ; j++) {
            if (vil[i][j] == 'K') {
                cnt_k++;
            }
            else if (vil[i][j] == 'P') {
                y_post = i, x_post = j;
            }
        }
    }
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < n ; j++) {
            scanf("%d", &h[i][j]);
            hhh.push_back(h[i][j]);
        }
    }
    // 하고 싶은 것
    // 낮은 높이, 높은 높이를 임의로 정해서 모든 집에 배달 할 수 있는지를 확인하고 싶다 

    //if (bfs(low, high) == cnt_k) ==> OK
    // low, high 모든 경우를 탐색하면 시간이 오래걸릴텐데......
    // 1. 이분 탐색을 이용 ==> hint : 특정 low에 대해서 되는 low + "a" 를 찾아보기
    // 2. 투포인터를 이용 ==> hint : 특정 시점에서 low-high가 만족을 했을때 다음 스텝은? 
    sort(hhh.begin(), hhh.end());
    int answer = hhh.back() - hhh[0];
    for (int low = 0, high = 0 ; low < hhh.size() && high < hhh.size() && low <= high ; ) {
        if (bfs(hhh[low], hhh[high]) == cnt_k) {
            int tmp = hhh[high] - hhh[low];
            if (tmp < answer) {
                answer = tmp;
            }
            low++;
        }
        else {
            high++;
        }
    }
    printf("%d", answer);
}

• 완전 탐색

  1) 가장 낮은 높이

  2) 가장 높은 높이

  • 위의 두가지를 임의 지정해서 그 범위만을 탐색하는 방법