문제
가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 0과 1로 나타나 있다. 1은 아직 잘려지지 않은 나무를 나타내고 0은 아무 것도 없음을 나타낸다. 다음 지형을 보자.
B 0 0 1 1 B 0 0 0 0 B 0 0 0 0 1 1 0 0 0 E E E 0 0
위의 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 하는 문제를 생각해 보자. BBB와 EEE의 위치는 임의로 주어진다. 단 문제에서 통나무의 길이는 항상 3이며 B의 개수와 E의 개수는 같다. 통나무를 움직이는 방법은 아래와 같이 상하좌우(Up, Down, Left, Right)와 회전(Turn)이 있다.
| 코드 | 의미 |
|---|---|
| U | 통나무를 위로 한 칸 옮긴다. |
| D | 통나무를 아래로 한 칸 옮긴다. |
| L | 통나무를 왼쪽으로 한 칸 옮긴다. |
| R | 통나무를 오른쪽으로 한 칸 옮긴다. |
| T | 중심점을 중심으로 90도 회전시킨다. |
예를 들면, 다음과 같다. (초기상태로부터의 이동)
| 초기상태 | 상(U) | 하(D) | 좌(L) | 우(R) | 회전(T) |
|---|---|---|---|---|---|
0 0 0 0 0 0 | 0 0 0 0 0 0 | 0 0 0 0 0 0 | 0 0 0 0 0 0 | 0 0 0 0 0 0 | 0 0 0 0 0 0 |
이와 같은 방식으로 이동시킬 때에 그 움직일 위치에 다른 나무, 즉 1이 없어야만 움직일 수 있다. 그리고 움직임은 위의 그림과 같이 한 번에 한 칸씩만 움직인다. 단 움직이는 통나무는 어떤 경우이든지 중간단계에서 한 행이나 한 열에만 놓일 수 있다. 예를 들면 아래 그림에서 a와 같은 단계는 불가능하다. 그리고 회전의 경우에서는 반드시 중심점을 중심으로 90도 회전을 해야 한다. (항상 통나무의 길이가 3이므로 중심점이 있음)
그리고 이런 회전(Turn)이 가능하기 위해서는 그 통나무를 둘러싸고 있는 3*3 정사각형의 구역에 단 한 그루의 나무도 없어야만 한다. 즉, 아래그림 b, d와 같이 ?로 표시된 지역에 다른 나무, 즉 1이 없어야만 회전시킬 수 있다. 따라서 c와 같은 경우에, 통나무는 왼쪽 아직 벌채되지 않은 나무 때문에 회전시킬 수 없다.
| a | b | c | d |
|---|---|---|---|
0 0 0 0 0 0 | 0 0 0 0 0 0 | 0 0 0 0 0 0 | 0 0 0 0 0 0 |
문제는 통나무를 5개의 기본동작(U, D, L, R, T)만을 사용하여 처음위치(BBB)에서 최종위치(EEE)로 옮기는 프로그램을 작성하는 것이다. 단, 최소 횟수의 단위 동작을 사용해야 한다.
입력
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.
출력
첫째 줄에 최소 동작 횟수를 출력한다. 이동이 불가능하면 0만을 출력한다.
예제 입력 1
5
B0011
B0000
B0000
11000
EEE00예제 출력 1
9풀이
이 문제는 BFS 알고리즘을 이용해서 풀었다. 생각한 이론대로 구현을 했더니 한번에 풀 수 있었던 문제였으나 bfs() 메소드 안의 코드들을 따로 빼서 별도의 메소드를 만든다면 코드가 더 정렬돼 보일 수 있을 것 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static char[][] map;
static int N;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new char[N][N];
int[] log = new int[6];
int[] fin = new int[6];
int idx1 = 0;
int idx2 = 0;
Log temp; //통나무 클래스 state의 값 가로: 0 세로: 1
Log out;
for(int i=0; i<N; i++) {
String input = br.readLine();
for(int j=0; j<N; j++) {
char c = input.charAt(j);
if(c=='B') {
log[idx1] = i;
idx1++;
log[idx1] = j;
idx1++;
map[i][j] = '0';
}
else if(c=='E') {
fin[idx2] = i;
idx2++;
fin[idx2] = j;
idx2++;
map[i][j] = '0';
}
else
map[i][j] = c;
}
}
if(log[0]==log[2] && log[2]==log[4])
temp = new Log(log[2], log[3], 0, 0);
else
temp = new Log(log[2], log[3], 1, 0);
if(fin[0]==fin[2] && fin[2]==fin[4])
out = new Log(fin[2], fin[3], 0, 0);
else
out = new Log(fin[2], fin[3], 1, 0);
bfs(temp, out);
}
public static void bfs(Log log, Log out) {
Queue<Log> queue = new LinkedList<>();
boolean[][][] visited = new boolean[N][N][2];
visited[log.x][log.y][log.state] = true;
queue.add(new Log(log.x, log.y, log.state, 0));
while(!queue.isEmpty()) {
Log temp = queue.poll();
Log after = new Log(0, 0, 0, 0);
if(temp.x==out.x && temp.y==out.y && temp.state==out.state) {
System.out.println(temp.t);
return;
}
for(int i=0; i<5; i++) {
if(i==0) {
if((temp.state==0 && temp.x==0) || (temp.state==1 && temp.x==1)) continue;
if((temp.state==0 && (map[temp.x-1][temp.y]=='1'|| map[temp.x-1][temp.y-1]=='1' || map[temp.x-1][temp.y+1]=='1')) || (temp.state==1 && (map[temp.x-2][temp.y]=='1'))) continue;
after = new Log(temp.x-1, temp.y, temp.state, temp.t+1);
}
else if(i==1) {
if((temp.state==0 && (temp.x==N-1 || map[temp.x+1][temp.y]=='1'|| map[temp.x+1][temp.y-1]=='1' || map[temp.x+1][temp.y+1]=='1')) || (temp.state==1 && (temp.x==N-2 || map[temp.x+2][temp.y]=='1'))) continue;
after = new Log(temp.x+1, temp.y, temp.state, temp.t+1);
}
else if(i==2) {
if((temp.state==0 && (temp.y==1 || map[temp.x][temp.y-2]=='1')) || (temp.state==1 && (temp.y==0 || map[temp.x-1][temp.y-1]=='1'|| map[temp.x][temp.y-1]=='1' || map[temp.x+1][temp.y-1]=='1'))) continue;
after = new Log(temp.x, temp.y-1, temp.state, temp.t+1);
}
else if(i==3) {
if((temp.state==0 && (temp.y==N-2 || map[temp.x][temp.y+2]=='1')) || (temp.state==1 && (temp.y==N-1 || map[temp.x-1][temp.y+1]=='1'|| map[temp.x][temp.y+1]=='1' || map[temp.x+1][temp.y+1]=='1'))) continue;
after = new Log(temp.x, temp.y+1, temp.state, temp.t+1);
}
if(i==4) {
if(temp.state==0) {
if (temp.x==0 || temp.x==N-1 || map[temp.x-1][temp.y-1] == '1' || map[temp.x - 1][temp.y] == '1' || map[temp.x - 1][temp.y + 1] == '1' || map[temp.x + 1][temp.y - 1] == '1' || map[temp.x + 1][temp.y] == '1' || map[temp.x + 1][temp.y + 1] == '1')
continue;
after = new Log(temp.x, temp.y, 1-temp.state, temp.t+1);
}
else {
if(temp.y==0 || temp.y>=N-1 || map[temp.x-1][temp.y-1]=='1' || map[temp.x][temp.y-1]=='1' || map[temp.x+1][temp.y-1]=='1' || map[temp.x-1][temp.y+1]=='1' || map[temp.x][temp.y+1]=='1' || map[temp.x+1][temp.y+1]=='1') continue;
after = new Log(temp.x, temp.y, 1-temp.state, temp.t+1);
}
}
if(!visited[after.x][after.y][after.state]) {
visited[after.x][after.y][after.state] = true;
queue.add(after);
}
}
}
System.out.println(0);
}
public static class Log {
int x;
int y;
int state;
int t;
public Log(int x, int y, int state, int t) {
this.x = x;
this.y = y;
this.state = state;
this.t = t;
}
}
}
