1938 통나무옮기기
가로, 세로의 길이가 같은 평지에서 벌목을 한다.
1은 잘리지 않은 나무, 0은 아무것도 없음을 나타낸다.
이 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 한다.
문제에서 통나무의 길이는 항상 3이며 B의 개수와 E의 개수는 같다.
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
통나무를 움직이는 방법은 상하좌우, 회전이 있고 움직일 위치에 1이 없어야 가능하다.
회전이 가능하기 위해서는 통나무를 둘러싼 3*3 정사각형 내에 1이 없어야 한다.
나무를 EEE까지 옮기는 최소 횟수를 구해라.
풀이
BFS를 이용하여 객체에 cnt를 저장하면서 이동해야 한다.
- 처음으로 통나무의 상태를 저장할 객체 Tree를 만들어준다.
- Tree에는 현재좌표, 나무의 방향(세로, 가로), 횟수를 저장한다.
- 입력을 받을 때 List를 사용하여 최초 BBB의 좌표와 EEE의 좌표를 저장한다.
- 항상 두 번째로 받는 값이 중심 좌표이다.
- 입력받은 리스트에서 첫 요소의 y좌표와 다음 요소의 y좌표가 같으면 가로 모양이다.
- 모양은 rot와 endR변수에 저장하고 0 : 세로, 1 : 가로로 설정하였다.
- 통나무를 움직일수 있는지 확인하는 메소드
checkMove를 구현한다. : boolean 리턴- map과 Tree객체, 방향을 파라미터로 받는다.
- 방향에 따라 구현하고 내부에서도 움직일 방향에 따라 1이 있는지 확인하거나, 맵 외부로 넘어가는지 확인한다.
- 통나무가 회전할 수 있는지 확인하는 메소드
checkRotate를 구현한다. : boolean 리턴- map과 통나무의 중심 좌표를 파라미터로 받는다.
- 좌표를 기준으로 3*3내에 1이 없는지 외부로 넘어가는지 확인한다.
- BFS를 사용하여 이동을 한다.
- 방문확인 배열은 삼차원으로 구현하여 통나무의 현재 상태에 따라 다르게 방문을 체크할 수 있도록 구현한다.
- queue는 Tree 객체를 받을 수 있도록한다.
- while이 시작할 때 회전이 가능한지, 방문이 가능한지 확인하고 가능하면 cnt를 하나 올린뒤 queue에 넣어준다.
- 델타 배열을 사용해서 0:위, 1:오, 2:아, 3:왼 으로 나올 수 있게 한다.
- for문을 사용해
checkMove가 가능하고 방문하지 않았다면 cnt를 올린 뒤 queue에 넣어준 후 좌표와 방향에 맞는 방문배열에 체크 해준다. - while이 시작할 때 현재 큐의 좌표와 방향이 E의 좌표와 맞는지 확인하고 맞다면 ans에 최소값을 넣어준다.
- 현재 cnt가 ans보다 크다면 작업을 하지 않도록 구현한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class 통나무옮기기{
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
char[][] map = new char[N][N];
List<int[]> trees = new ArrayList<>();
List<int[]> end = new ArrayList<>();
for(int i = 0; i < N; i++) {
String str = br.readLine();
for(int j = 0; j < N; j++) {
map[i][j] = str.charAt(j);
if(map[i][j] == 'B') {
trees.add(new int[] {i,j});
}
if(map[i][j] == 'E') {
end.add(new int[] {i,j});
}
}
}
int rot= 0; // 0 세로, 1가로
if(trees.get(1)[0]==trees.get(0)[0]&& trees.get(0)[0]==trees.get(2)[0]) { //가로
rot = 1;
}
int endR = 0;
if(end.get(0)[0]==end.get(1)[0]) {
endR = 1;
}
Tree finish = new Tree(end.get(1)[0], end.get(1)[1], endR, 0);
Tree first = new Tree(trees.get(1)[0], trees.get(1)[1], rot, 0);
int ans = Integer.MAX_VALUE;
int[][][] visited = new int[N][N][2];
visited[first.y][first.x][first.r]++;
Queue<Tree> queue = new LinkedList<>();
queue.add(first);
while(!queue.isEmpty()) {
int y = queue.peek().y;
int x = queue.peek().x;
int r = queue.peek().r;
int cnt = queue.peek().cnt;
Tree pick = queue.poll();
if(finish.y == y && finish.x == x && finish.r == r) {
ans = Math.min(ans, cnt);
}
if(ans > cnt) {
if(checkRotate(map, y, x) ) {
if(r == 1 && visited[y][x][0] == 0) {
queue.add(new Tree(y, x, 0, cnt+1));
}else if(r == 0 && visited[y][x][1] == 0) {
queue.add(new Tree(y, x, 1, cnt+1));
}
}
for(int i = 0; i < 4; i++) {
if(checkMove(map, new Tree(y+dy[i], x+dx[i], r, cnt), i) && visited[y+dy[i]][x+dx[i]][r] == 0) {
queue.add(new Tree(y+dy[i], x+dx[i], r, cnt+1));
visited[y+dy[i]][x+dx[i]][r]++;
}
}
}
}
if(ans == Integer.MAX_VALUE) {
ans = 0;
}
System.out.println(ans);
}
static int N;
static int[] dy = {-1,0,1,0};
static int[] dx = {0,1,0,-1};
//dir : 0위 1오 2아 3왼
static boolean checkMove(char[][] map, Tree tree, int dir) {
int y = tree.y;
int x = tree.x;
int r = tree.r;
boolean chk = true;
if(r == 0) { //세로
if(dir == 0) {
if(y-1 < 0 || map[y-1][x] == '1') chk = false;
}else if(dir == 1) {
if(x >= N || y+1 >= N || y-1 < 0 || map[y][x] == '1' ||
map[y-1][x] == '1' || map[y+1][x] == '1') chk = false;
}else if(dir == 2) {
if(y+1 >= N || map[y+1][x] == '1') chk = false;
}else if(dir == 3) {
if(x < 0 || y+1 >= N || y-1 < 0 || map[y][x] == '1' ||
map[y-1][x] == '1' || map[y+1][x] == '1') chk = false;
}
}else { //가로
if(dir == 0) {
if(y < 0 || x+1 >= N || x-1 < 0 || map[y][x] == '1' ||
map[y][x-1] == '1' || map[y][x+1] == '1') chk = false;
}else if(dir == 1) {
if(x+1 >= N || map[y][x+1] == '1') chk = false;
}else if(dir == 2) {
if(y >= N || x+1 >= N || x-1 < 0 || map[y][x] == '1' ||
map[y][x-1] == '1' || map[y][x+1] == '1') chk = false;
}else if(dir == 3) {
if(x-1 < 0 || map[y][x-1] == '1') chk = false;
}
}
return chk;
}
static boolean checkRotate(char[][] map, int y, int x) {
if(y-1 < 0 || x-1 < 0 || y+1 >= N || x+1 >= N)return false;
for(int i = y-1; i <= y+1; i++) {
for(int j = x-1; j <= x+1; j++) {
if(map[i][j] == '1')return false;
}
}
return true;
}
}
class Tree{
int y;
int x;
int r;
int cnt;
public Tree(int y, int x, int r, int cnt) {
this.y = y;
this.x = x;
this.r = r;
this.cnt = cnt;
}
}