[BOJ] 통나무 옮기기

Posted on | In |

문제

가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 0과 1로 나타나 있다. 1은 아직 잘려지지 않은 나무를 나타내고 0은 아무 것도 없음을 나타낸다. 다음 지형을 보자.

1
2
3
4
5
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도 회전시킨다.

문제는 통나무를 5개의 기본동작(U, D, L, R, T)만을 사용하여 처음위치(BBB)에서 최종위치(EEE)로 옮기는 프로그램을 작성하는 것이다. 단, 최소 횟수의 단위 동작을 사용해야 한다.

제한사항

이외의 제한사항은 없다.

첫번째 생각

통나무의 좌표를 저장하려고 X1,X2,X3,Y1,Y2,Y3를 저장해야 된다고 생각했지만,

항상 통나무의 중심좌표를 기준으로 움직인다고 생각하고 통나무의 상태를 기록하면 중심좌표만 기록하면 된다.

통나무의 중심 좌표 구하는법

B B B의 모든 X , Y 좌표를 더한뒤 3으로 나눈다. 그러면 중심좌표를 구할 수 있다.

통나무를 구석에서 옮긴다면 어떻게 될 것인가에 대한 의문이 있는 문제였다.

통나무를 구석에서 옮기는 상황은 고려하지 않고 코드를 작성했지만 통과하는데 문제는 없었다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[] dx = {0,0,-1,1,0};
	static int[] dy = {-1,1,0,0,0};
	static int[] ds = {0,0,0,0,1}; // 회전 여부 확인
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.nextLine();
		char[][] map = new char[N][N];
		boolean[][][] visit = new boolean[N][N][2]; // 통나무 방향까지 저장
		for(int y=0; y<N; y++) {
			map[y] = sc.nextLine().toCharArray();
		}
		LOG start = new LOG(0,0,0,0);
		LOG dest = new LOG(0,0,0,0);
		for(int y=0; y<N; y++) {
			for(int x=0; x<N; x++) {
				if ( map[y][x] == 'B' ) { // 통나무의 시작 좌표
					map[y][x] = '0';
					start.count++;
					if ( start.count == 2 ) { // 첫 좌표와 같은 좌표가 들어온다면 상태를 볼 수 있다.
						// X좌표가 동일하다면 | 모양일 것이고, Y좌표가 동일하다면 ㅡ 모양일 것이다.
						if ( start.X == x ) {
							start.S = 0;
						} else if ( start.Y == y ) {
							start.S = 1;
						}
					}
					start.X += x;
					start.Y += y;
				} else if ( map[y][x] == 'E' ) {
					map[y][x] = '0';
					dest.count++;
					if ( dest.count == 2 ) {
						if ( dest.X == x ) {
							dest.S = 0;
						} else if ( dest.Y == y ) {
							dest.S = 1;
						}
					}
					dest.X += x;
					dest.Y += y;
				}
			}
		}
		start.X = start.X/3; start.Y = start.Y/3;
		dest.X = dest.X/3; dest.Y = dest.Y/3;
		start.count = 0;
		dest.count = 0;
		Queue<LOG> q = new LinkedList<LOG>();
		q.add(start);
		visit[start.Y][start.X][start.S] = true;
		int ans = 0;
		while(!q.isEmpty()) {
			LOG log = q.poll();
			if( log.X == dest.X && log.Y == dest.Y && log.S == dest.S ) {
				ans = log.count;
				break;
			}
			for(int cmd=0; cmd<5; cmd++) {
				// cmd == 0 : U cmd == 1 : D cmd == 2 : L cmd == 3 : R cmd == 4 : T
				int tempX = log.X + dx[cmd];
				int tempY = log.Y + dy[cmd];
				int tempS = (log.S + ds[cmd])%2; // 0이었다면 1이되고, 1이었다면 0이된다.
				if (cmd == 4) {
					if (InRangeByS(tempX, tempY, tempS, N) && InRangeByS(tempX, tempY, (tempS + 1) % 2, N)
						&& InRange(tempX - 1, tempY - 1, N) && InRange(tempX + 1, tempY + 1, N)) {
						if ( map[tempY-1][tempX] == '0' && map[tempY+1][tempX] == '0' &&
							 map[tempY][tempX-1] == '0' && map[tempY][tempX+1] == '0' &&
							 map[tempY-1][tempX+1] == '0' && map[tempY+1][tempX-1] == '0' &&
							 map[tempY-1][tempX-1] == '0' && map[tempY+1][tempX+1] == '0') { // 갈 수 있다면
							if (!visit[tempY][tempX][tempS]) {
								visit[tempY][tempX][tempS] = true;
								q.add(new LOG(tempX, tempY, tempS, log.count + 1));
							}
						}
					}
				} else {
					if (InRangeByS(tempX, tempY, tempS, N) && canMove(tempX, tempY, tempS, map)) {
						if (!visit[tempY][tempX][tempS]) {
							visit[tempY][tempX][tempS] = true;
							q.add(new LOG(tempX, tempY, tempS, log.count + 1));
						}
					}
				}
			}
			
		}
		System.out.println(ans);
		
	}
	public static boolean canMove(int x,int y,int s,char[][] map) {
		if ( s == 0 ) {
			if( map[y-1][x] == '0' && map[y][x] == '0' && map[y+1][x] == '0' ) {
				return true;
			}
		}
		else if ( s == 1 ) {
			if( map[y][x-1] == '0' && map[y][x] == '0' && map[y][x+1] == '0' ) {
				return true;
			}
		}
		return false;
	}
	public static boolean InRangeByS(int x,int y,int s,int N) {
		if ( s == 0 ) { // | 모양이므로 y-1 y+1 체크
			if ( InRange(x,y,N) && InRange(x,y-1,N) && InRange(x,y+1,N) ) {
				return true;
			}	
		} else if ( s == 1 ) {
			if ( InRange(x,y,N) && InRange(x-1,y,N) && InRange(x+1,y,N) ) {
				return true;
			}
		}
		return false;
	}
	
	public static boolean InRange(int x,int y,int N) {
		if (x>=0 && y>=0 && x<N && y<N ) {
			return true;
		}
		return false;
	}
	public static class LOG {
		int X;
		int Y;
		int S; 
		// S == 0 : |
		// S == 1 : ㅡ
		int count;
		LOG(int x,int y,int s,int c) {
			X=x;
			Y=y;
			S=s;
			count=c;
		}
	}
	
}