[백준]1938 통나무 옮기기 -JAVA //le_effort//

통나무 옮기기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	5278	1513	1103	27.679%

문제

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

xxxxxxxxxx
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 **B B B** 0 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 **B B B** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 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 **B B B** 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 **B B B** 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 **B B B** 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 **B** 0 0 0 0 0 **B** 0 0 0 0 0 **B** 0 0 0 0 0 0 1 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 B 0 0 0 0 B 0 0 0 0 B 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 ? ? ? 0 0 0 **B B B** 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 **B** 0 0 0 0 0 **B** 0 0 0 0 0 **B** 0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 ? **B** ? 0 0 0 ? **B** ? 0 0 0 ? **B** ? 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 복사

xxxxxxxxxx
5
B0011
B0000
B0000
11000
EEE00

예제 출력 1 복사

9

 

풀이

bfs + 구현

 

요새 스프링 공부를 하느라 알고리즘을 자주 안 풀었더니 기초적인 실수를 많이 해서 애를 먹었다;;

char형 배열에서 map[i][j]=='1' 이렇게 해야하는데 map[i][j]==1 이렇게 하는 실수도 하고 오래걸렸다.

 

통나무의 길이는 3으로 고정되어 있으니 가운데 좌표값만 받는다

class에는 x좌표 y좌표 방향 cnt로 지정했다.

 

그리고 구현을 하면 된다.

 

전체코드

import java.io.*;
import java.util.*;
public class Main {
    static char map[][];
    static int n;
    static int dx[]= {-1,-1,-1,1,1,1,0,0};
    static int dy[] = {-1,0,1,-1,0,1,-1,1};
    static boolean visited[][][];
    static Node end = new Node(0,0,0,0);
    static Queue<Node> q = new LinkedList<>();
    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];
        visited = new boolean[n][n][2];
        for(int i=0; i<n; i++) {
            String str = br.readLine();
            for(int j=0; j<n; j++) {
                map[i][j]=str.charAt(j);
            }
        }
        
        boolean flag= true;
        
        for(int i=0; i<n; i++) {
            if(!flag) {
                break;
            }
            for(int j=0; j<n; j++) {
                if(map[i][j]=='B') {
                    if(i+1<n && map[i+1][j]=='B') {
                        q.add(new Node(i+1,j,0,0));
                        flag = false;
                        break;
                    }
                    else if(j+1<n && map[i][j+1]=='B') {
                        q.add(new Node(i,j+1,1,0));
                        flag = false;
                        break;
                    }
                }
            }
        }
        
        flag=true;
        for(int i=0; i<n; i++) {
            if(!flag) {
                break;
            }
            for(int j=0; j<n; j++) {
                if(map[i][j]=='E') {
                    if(i+1<n &&map[i+1][j]=='E') {
                        end.x=i+1;
                        end.y=j;
                        end.shape=0;
                        flag = false;
                        break;
                    }
                    else if(j+1<n && map[i][j+1]=='E') {
                        end.x=i;
                        end.y=j+1;
                        end.shape=1;
                        flag = false;
                        break;
                    }
                }
            }
        }
​
        bfs();
    }
    public static void bfs() {
        while(!q.isEmpty()) {
            Node a = q.poll();
            int x=a.x;
            int y= a.y;
            int rotate_cnt=0;
            int shape =a.shape;
            if(a.x==end.x && a.y==end.y && a.shape == end.shape) {
                System.out.println(a.cnt);
                return;
            }
            for(int i=0; i<8; i++) {
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(nx>=0 && ny>=0 && nx<n && ny<n && map[nx][ny]!='1') {
                    rotate_cnt++;
                }
            }
            if(rotate_cnt==8) {
                if(shape==0) {
                    if(!visited[x][y][1]) {
                        q.add(new Node(x,y,1,a.cnt+1));
                        visited[x][y][1]=true;
                    }
                }
                else {
                    if(!visited[x][y][0]) {
                        q.add(new Node(x,y,0,a.cnt+1));
                        visited[x][y][0]=true;
                    }
                }
            }
            
            if(shape ==0) { // 세로 일 때
                if(x-2>=0 && !visited[x-1][y][shape] && map[x-2][y]!='1') { // U
                    q.add(new Node(x-1,y,shape,a.cnt+1));
                    visited[x-1][y][shape]=true;
                }
                if(x+2<n && !visited[x+1][y][shape] && map[x+2][y]!='1') {  // D
                    q.add(new Node(x+1,y,shape,a.cnt+1));
                    visited[x+1][y][shape]=true;
                }
                if(y-1>=0 && !visited[x][y-1][shape] && map[x-1][y-1]!='1' && map[x][y-1]!='1' && map[x+1][y-1]!='1') { //L
                    q.add(new Node(x,y-1,shape,a.cnt+1));
                    visited[x][y-1][shape]=true;
                }
                if(y+1<n && !visited[x][y+1][shape] && map[x-1][y+1]!='1' && map[x][y+1]!='1' && map[x+1][y+1]!='1') { //L
                    q.add(new Node(x,y+1,shape,a.cnt+1));
                    visited[x][y+1][shape]=true;
                }
            }
            else {  // 가로일때
                if(x-1>=0 && !visited[x-1][y][shape] && map[x-1][y]!='1' && map[x-1][y+1]!='1' && map[x-1][y-1]!='1') { //U
                    q.add(new Node(x-1,y,shape,a.cnt+1));
                    visited[x-1][y][shape]=true;
                }
                if(x+1<n && !visited[x+1][y][shape] && map[x+1][y]!='1' && map[x+1][y+1]!='1' && map[x+1][y-1]!='1') {  //D
                    q.add(new Node(x+1,y,shape,a.cnt+1));
                    visited[x+1][y][shape]=true;
                }
                if(y-2>=0 && !visited[x][y-1][shape] && map[x][y-2]!='1') { //L
                    q.add(new Node(x,y-1,shape,a.cnt+1));
                    visited[x][y-1][shape]=true;
                }
                if(y+2<n && !visited[x][y+1][shape] && map[x][y+2]!='1') {//R
                    q.add(new Node(x,y+1,shape,a.cnt+1));
                    visited[x][y+1][shape]=true;
                }
            }
        }
        System.out.println(0);
    }
  }
class Node{
    int x,y,shape,cnt;
    Node(int x, int y, int shape, int cnt){
        this.x=x;
        this.y=y;
        this.shape=shape;
        this.cnt=cnt;
    }
}