[BOJ] 백준 22116 창영이와 퇴근 - Python/Java

문제

https://www.acmicpc.net/problem/22116

22116번: 창영이와 퇴근

해설

이 문제는 시작점부터 도착점까지 이동하면서 경로상의 최대 경사의 최소값을 찾는 문제로 BFS와 이분탐색을 이용하여 해결할 수 있습니다.

 

BFS는 그래프의 최단 경로를 구할 때도 사용할 수 있지만, 이 문제에서는 모든 경로를 완전 탐색하는데도 사용할 수 있는데요. 현재 지점을 기준으로 네 방향을 바라보고, 네 방향 중에서 현재 임계값(최대 경사로 정한 값)보다 경사가 작거나 같고, 방문하지 않았다면 그 곳을 이동 가능한 영역으로 보기 때문입니다.

 

다시 말해서, 간단한 BFS 구현을 생각해보면 상하좌우의 네 방향을 보고, 아직 방문하지 않았다면 큐에 해당 지점을 삽입하는데요. 이 문제에서는 이 조건에 더해 '임계값을 넘지 않으면'이라는 조건이 더해지기 때문에 최단 경로로 이동함을 보장하지 않게 됩니다. 아래 예시를 보겠습니다.

 

예시

위와 같은 예시에서 시작점(1,1)에서 움직일 수 있는 곳은 (2,1)밖에 없으며, (2,1)에서는 (2,2)로만 이동 가능합니다. 그리고 (2,2)에서는 (1,2)로 이동할 수 있는데요. 이전에 (1,1)에서 (2,1)을 방문할 수 없었기 때문에 (2,2)에 와서야 (1,2)로 이동할 수 있게 되는 것입니다. 이런 식으로 이동을 반복하면 최단 경로로 끝점까지 가지는 못하지만, 임계값 50을 넘기지 않고 도착점까지 이동이 가능합니다. 

 

따라서 BFS를 이용하게 되면 시작점부터 끝점까지의 모든 경사로를 탐색할 수 있게 되는데 이 때 임계값을 넘기지 않으면서 끝점까지 도착할 수 있다면 경사로의 최대값은 해당 임계값을 넘기지 않는다는 뜻이 됩니다.

 

여기서 임계값이란, 이분탐색을 이용해서 그래프의 경사로 최대값을 설정하여 BFS에 넘겨주는 값인데요. 예를 들어 5000이라는 값이 그래프의 최대 경사의 최소값인가?를 확인했을 때 가능하다면 5000보다 작은 값을 넣어보고, 불가능하다면 5000보다 큰 값을 넣어보는 것이죠. 이 때, 단순히 1씩 증감을 하는 완전탐색이 아니라 이분탐색을 해서 logN 시간안에 가능한 최적의 임계값을 찾아낼 수 있는 것입니다.

 

위 내용을 코드로 옮기면 아래와 같습니다.

 

풀이 - 파이썬

import sys
from collections import deque
def bfs(target):
    q = deque()
    visited = [[False] * n for _ in range(n)]
    visited[0][0] = True
    q.append((0,0))

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if not visited[nx][ny]:
                    if abs(graph[nx][ny] - graph[x][y]) <= target:
                        if nx == n-1 and ny == n-1: return True
                        visited[nx][ny] = True
                        q.append((nx,ny))
    return False


input = sys.stdin.readline
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
answer, lower, upper = 0, 0, 1000000000
while lower <= upper:
    mid = (lower + upper) // 2
    if bfs(mid):
        answer = mid
        upper = mid - 1
    else:
        lower = mid + 1
print(answer)

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B_22116 {
    static int n;
    static int[][] graph;
    static int lower = 0;
    static int upper = 1000000000;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        graph = new int[n][n];
        for(int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < n; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int answer = 0;
        while(lower <= upper){
            int mid = (lower + upper) / 2;
            if(bfs(mid)){
                answer = mid;
                upper = mid - 1;
            }else{
                lower = mid + 1;
            }
        }
        System.out.println(answer);
    }

    static boolean bfs(int target){
        boolean[][] visited = new boolean[n][n];
        LinkedList<Point> q = new LinkedList<>();

        visited[0][0] = true;
        q.add(new Point(0, 0));

        while (!q.isEmpty()) {
            Point p = q.pollFirst();
            int x = p.x; int y = p.y;
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i], ny = y+dy[i];
                if(0 <= nx && nx < n && 0 <= ny && ny < n){
                    if(!visited[nx][ny] && Math.abs(graph[nx][ny]-graph[x][y]) <= target){
                        if(nx == n-1 && ny == n-1) return true;
                        visited[nx][ny] = true;
                        q.add(new Point(nx, ny));
                    }
                }
            }
        }
        return false;
    }

    static class Point{
        int x, y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}