[백준]#17267 상남자

문제

CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하지 않는다. 하지만 영조의 행동이 답답한 영조의 친구 보성이는 영조가 위, 아래로만 가는 걸 막기 위해 영조와 같이 다니며 왼쪽으로 최대 L번 오른쪽으로 최대 R번만큼 이동할 수 있게 영조를 도와준다. 영조와 보성이는 지도 밖으로는 나가지 않는다.

갈수 있는 땅, 벽의 위치, 영조와 보성이의 출발 위치가 지도 정보로 주어졌을 때 영조와 보성이가 출발 위치로부터 이동해서 갈 수 있는 모든 땅의 개수를 구해보자.

다음은 이해를 돕기 위한 예제1 그림이다.

영조와 보성이가 시작 위치에서 갈수 있는 땅은 파란색, 벽이 있어 갈수 없는 땅은 검은색이다.

다음 그림은 영조와 보성이가 시작 위치에서 왼쪽으로 한 칸 이동했을 때이다.

왼쪽으로 한 칸 이동하였으므로 더 이상 왼쪽으로는 갈 수 없고, 현재 상태에서 갈수 있는 길은 파란색으로 나타내었다.

다음 그림은 영조와 보성이가 시작 위치에서 아래로 갔을 때이다.

영조와 보성이가 아래로 한 칸 이동했을 때의 갈 수 있는 땅과 현재 상태이다.

다음 그림은 영조와 보성이가 자유롭게 이동하였을 때 도달 가능한 땅을 나타낸다.

영조와 보성이가 최대 왼쪽으로 L번, 오른쪽으로 R번 만큼 움직여서 자유롭게 이동했을 때 도달 가능한 땅은 13칸이다.

입력

첫 번째 줄에 지도의 행과 열 N, M이 주어진다 (1 ≤ N, M ≤ 1,000)

두 번째 줄에 왼쪽과 오른쪽으로 갈수 있는 최대 횟수 L, R이 주어진다. (0 ≤ L, R ≤ M)

세 번째 줄부터 N+2줄까지 M 의 크기만큼 지도가 주어진다.

• 0: 갈 수 있는 땅
• 1: 벽이 있어 갈 수 없는 땅
• 2: 영조와 보성이가 있는 위치

출력

시작 위치를 포함하여 갈수 있는 땅의 개수를 출력한다.

예제 입력 1

5 5
1 1
00000
00000
02100
10000
00000

예제 출력 1

13

예제 입력 2

4 5
1 2
00000
11010
02011
10000

예제 출력 2

10

풀이

이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 풀 수 있었다. 처음에 4차원 배열을 이용해서 풀려고 했으나 메모리가 너무 커질 것 같아서 반려했다. 여기에서 중요한 포인트는 상,하는 제한이 없다는 것이다.

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

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] map;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");
        int L = Integer.parseInt(input[0]);
        int R = Integer.parseInt(input[1]);

        map = new int[N][M];
        Pair start = new Pair(0, 0, L, R);

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j) - '0';

                if(map[i][j]==2) {
                    start.x = i;
                    start.y = j;
                    map[i][j] = 0;
                }
            }
        }

        bfs(N, M, start);
    }

    public static void bfs(int N, int M, Pair start) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        int ans = 1;
        queue.add(start);
        visited[start.x][start.y] = true;

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            for(int i=0; i<4; i++) {
                int nx = temp.x;
                int ny = temp.y;

                if(i==0) {                //상, 하로 가는 방법은 횟수 제한이 없기 때문에 막히는 곳까지 갈 수 있는 모든  큐에 넣어줌
                    while(true) {
                        nx = nx+dx[i];
                        ny = ny+dy[i];

                        if(nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny]==1 || visited[nx][ny]) break;

                        visited[nx][ny] = true;
                        queue.add(new Pair(nx, ny, temp.l, temp.r));
                        ans++;
                    }
                }

                else if(i==1) {
                    while(true) {
                        nx = nx+dx[i];
                        ny = ny+dy[i];

                        if(nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny]==1 || visited[nx][ny]) break;

                        visited[nx][ny] = true;
                        queue.add(new Pair(nx, ny, temp.l, temp.r));
                        ans++;
                    }
                }

                else if(i==2) {               //좌,우는 한 칸씩 큐에 넣어줌
                    nx = nx+dx[i];
                    ny = ny+dy[i];

                    if(temp.l==0 || nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny]==1 || visited[nx][ny]) continue;

                    visited[nx][ny] = true;
                    queue.add(new Pair(nx, ny, temp.l-1, temp.r));
                    ans++;
                }

                else {
                    nx = nx+dx[i];
                    ny = ny+dy[i];

                    if(temp.r==0 || nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny]==1 || visited[nx][ny]) continue;

                    visited[nx][ny] = true;
                    queue.add(new Pair(nx, ny, temp.l, temp.r-1));
                    ans++;
                }
            }
        }

        System.out.println(ans);
    }

    public static class Pair {
        int x;            //행
        int y;            //열
        int l;            //왼쪽으로 갈 수 있는 횟수
        int r;            //오른쪽으로 갈 수 있는 횟수

        public Pair(int x, int y, int l, int r) {
            this.x = x;
            this.y = y;
            this.l = l;
            this.r = r;
        }
    }
}