문제
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;
}
}
}