[BOJ] 백준 16973 직사각형 탈출 - Python/Java

문제

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

16973번: 직사각형 탈출

해설

일반적인 너비우선탐색(BFS) 문제가  약간 변형된 문제입니다.

 

보통 격자점이 주어지고 너비 우선 탐색을 하는 문제에서는 이동(탐색)하는 주체가 단위 격자점의 크기와 동일한데요. 이 문제에서는 격자점의 일부를 이루는 직사각형이 이동(탐색)을 하는 주체로 설정된 것입니다.

 

따라서 기존의 BFS 문제를 풀 때와 달리 아래와 같이 고민해야 하는 부분이 생깁니다.

 

1) 상하좌우로 이동할 때, 어떤 기준으로 방문 체크를 할 것인가?

2) 상하좌우에 벽이 있을 때, 이동하지 못하는 것을 어떻게 체크할 것인가?

3) 상하좌우로 이동할 때, 범위 안에서 이동하는 것을 어떻게 체크할 것인가?

 

세 가지 포인트 중에서, 1번과 3번을 해결하기 위해서는 직사각형이 통째로 이동한다고 생각하지 말고 직사각형의 왼쪽 상단 모서리 하나만 이동한다고 생각하는 것이 편합니다. 그렇게 되면 왼쪽 상단 모서리가 동일한 지점을 방문한다는 것 자체가 직사각형이 동일한 위치로 이동한다는 것과 같은 뜻이 되기 때문입니다.

 

또한, 범위를 체크하는 방식에서도 왼쪽 상단 모서리를 기준으로 문제에서 주어진 높이와 너비(h, w)를 더해주기만 하면 되기 때문에 큰 어려움이 없습니다.

 

마지막으로 2)번 조건을 체크하기 위해서는 각 이동 방향(상하좌우)과 같은 방향에 있는 직사각형의 테두리를 관찰해야 합니다. 예를 들어, 직사각형을 오른쪽으로 이동시킬 때는 직사각형의 오른쪽 테두리에 대해서만 해당 위치에 벽이 있는가를 확인하면 되는 것이죠. 이 부분은 반복문을 통해 네 방향을 확인할 때, 동시에 해당 방향에 있는 직사각형의 테두리 좌표들을 추출하면 됩니다.

 

풀이는 아래와 같습니다.

 

 

풀이 - 파이썬

from collections import deque
import sys
input = sys.stdin.readline

def isNotWall(sx, sy, w, h, dir):
    if dir == 0:
        boundary = [(i,sy) for i in range(sx, sx+h)]
    elif dir == 1:
        boundary = [(i, sy+w-1) for i in range(sx, sx+h)]
    elif dir == 2:
        boundary = [(sx, i) for i in range(sy, sy+w)]
    else:
        boundary = [(sx+h-1, i) for i in range(sy, sy+w)]
    for x, y in boundary:
        if graph[x][y] == 1:
            return False
    return True

def isInBoundary(x, y, w, h):
    if 0 <= x and x + h - 1 < n:
        if 0 <= y and y + w - 1 < m:
            return True
    return False

def bfs():
    visited = [[0] * m for _ in range(n)]

    # 왼쪽 상단 모서리만을 기준으로 생각한다.
    q = deque()
    q.append((sx, sy))
    visited[sx][sy] = 0

    while q:
        currX, currY = q.popleft()
        if currX == ex and currY == ey:
            return visited[currX][currY]
        for i in range(4):
            nextX, nextY = currX + dx[i], currY + dy[i]
            if isInBoundary(nextX, nextY, w, h): # 범위 체크
                if not visited[nextX][nextY]: # 방문 체크
                    if isNotWall(nextX, nextY, w, h, i): # 벽 체크
                        visited[nextX][nextY] = visited[currX][currY] + 1
                        q.append((nextX, nextY))
    return -1

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
h, w, sx, sy, ex, ey = map(int, input().split())
sx, sy, ex, ey = sx-1, sy-1, ex-1, ey-1 # (0, 0)을 시작점으로 맞추기

dx, dy = [0,0,-1,1], [-1,1,0,0] # left, right, up, down
answer = bfs()
print(answer)

풀이 - 자바

package PS;

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

public class B_16973 {
    static int[] dx = {0,0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static char[][] graph;
    static int n, m, h, w, sx, sy, ex, ey;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new char[n][m];
        for(int i = 0; i < n; i++){
            String[] line = br.readLine().split(" ");
            for(int j = 0 ; j < m; j++){
                graph[i][j] = line[j].charAt(0);
            }
        }

        st = new StringTokenizer(br.readLine());
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        sx = Integer.parseInt(st.nextToken());
        sy = Integer.parseInt(st.nextToken());
        ex = Integer.parseInt(st.nextToken());
        ey = Integer.parseInt(st.nextToken());
        sx -= 1; sy -= 1; ex -= 1; ey -= 1; // (0, 0)을 시작점으로 맞추기
        int answer = bfs();
        System.out.println(answer);
    }

    public static boolean isNotWall(int x, int y, int dir){
        ArrayList<Point> boundary = new ArrayList<Point>();
        switch (dir){
            case 0:
                for(int i = x; i < x+h; i++)
                    boundary.add(new Point(i, y));
                break;

            case 1:
                for(int i = x; i < x+h; i++){
                    boundary.add(new Point(i, y+w-1));
                }
                break;
            case 2:
                for(int i = y; i < y+w; i++) {
                    boundary.add(new Point(x, i));
                }
                break;
            case 3:
                for(int i = y; i < y+w; i++){
                    boundary.add(new Point(x+h-1, i));
                }
                break;
        }
        for (Point point : boundary) {
            if(graph[point.x][point.y] == '1'){
                return false;
            }
        }
        return true;
    }

    public static boolean isInBoundary(int x, int y){
        return (0 <= x && x + h - 1 < n && 0 <= y && y + w - 1 < m);
    }

    public static int bfs(){
        int[][] visited = new int[n][m];

        // 왼쪽 상단 모서리만을 기준으로 생각한다.
        LinkedList<Point> q = new LinkedList<>();
        q.add(new Point(sx, sy));
        visited[sx][sy] = 0;

        while (!q.isEmpty()) {
            Point curr = q.poll();
            int currX = curr.x; int currY = curr.y;
            if(currX == ex && currY == ey) return visited[currX][currY];

            for(int i = 0; i < 4; i++){
                int nx = currX + dx[i]; int ny = currY + dy[i];
                if(isInBoundary(nx, ny)){
                    if(visited[nx][ny] == 0){
                        if(isNotWall(nx,ny, i)){
                            visited[nx][ny] = visited[currX][currY] + 1;
                            q.add(new Point(nx, ny));
                        }
                    }
                }
            }
        }
        return -1;
    }

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