[백준 1938] 통나무 옮기기

문제

가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 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 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만을 출력한다.

문제 풀이

카카오 블록이동하기 문제(dong-co.tistory.com/9

)랑 비슷한거 같다.

 

 

bfs를 통해 방문했던 곳은 체크하며 다시 가지않고 사방이동, 회전이 가능한지 체크한뒤 최단거리를 측정해주면 된다. 

 

 

최근 들어 문제를 꼼꼼하게 읽지 않는 경향이 있는 것 같다.

첨에는 이동 가능 체크시 col-1을 col로만 중복해서 적어서 찾느라 애먹고 또한

이동이 불가하면 0 을 출력하는 부분을 고려안해서 틀린 곳을 찾느라 시간이 걸렸다. 

 

소스코드

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Baekjoon1938 {
    static final int VERTICAL=0;
    static final int HORIZONTAL=1;
    static int mapSize;
 
    static int map[][];
    static boolean visited[][][];
    static int dirRow[]={0,1,0,-1,-1,-1,1,1};
    static int dirCol[]={1,0,-1,0,-1,1,-1,1};
    static Log start;
    static Log destination;
 
 
    public static void main(String[] args) throws IOException {
        inputData();
        bfs();
        if(destination.dist==Integer.MAX_VALUE)
            System.out.println(0);
        else
            System.out.println(destination.dist);
 
    }
 
    private static void bfs() {
        Queue<Log> q = new LinkedList<>();
        q.add(start);
        visited[start.row][start.col][start.dir] = true;
        while(!q.isEmpty()){
            Log cur = q.poll();
            //System.out.println(cur.row+","+cur.col+","+cur.dir+":"+cur.dist);
            if(cur.isEnd()){
                destination.dist = Math.min(destination.dist,cur.dist);
                continue;
            }
 
            //먼저 이동 체
            for(int d=0;d<4;d++){
                int nextRow = cur.row + dirRow[d];
                int nextCol = cur.col + dirCol[d];
 
                if(!isAbleToMove(nextRow,nextCol,cur.dir))
                    continue;
                if(visited[nextRow][nextCol][cur.dir])
                    continue;
                visited[nextRow][nextCol][cur.dir] = true;
                q.add(new Log(nextRow,nextCol,cur.dir,cur.dist+1));
            }
            //회전
            if(isAbleToTurn(cur)){
                int nextDir = (cur.dir+1)%2;
                if(visited[cur.row][cur.col][nextDir])
                    continue;
                visited[cur.row][cur.col][nextDir] = true;
                q.add(new Log(cur.row,cur.col,nextDir,cur.dist+1));
            }
 
        }
 
    }
 
    private static boolean isAbleToTurn(Log cur){
        for(int i=0;i<8;i++){
            int r = cur.row + dirRow[i];
            int c = cur.col + dirCol[i];
            if(r<0||r>=mapSize||c<0||c>=mapSize)
                return false;
            if(map[r][c]==1)
                return false;
        }
        return true;
    }
    private static boolean isAbleToMove(int nextRow, int nextCol, int dir) {
        if(dir==VERTICAL){
            if(nextRow<0||nextRow>=mapSize||nextCol-1<0||nextCol+1>=mapSize)
                return false;
            if(map[nextRow][nextCol+1]==1||map[nextRow][nextCol-1]==1||map[nextRow][nextCol]==1)
                return false;
        }else{
            if(nextRow-1<0||nextRow+1>=mapSize||nextCol<0||nextCol>=mapSize)
                return false;
            if(map[nextRow+1][nextCol]==1||map[nextRow-1][nextCol]==1||map[nextRow][nextCol]==1)
                return false;
        }
        return true;
    }
 
    public static void inputData() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        mapSize = Integer.parseInt(br.readLine());
        map = new int[mapSize][mapSize];
        visited = new boolean[mapSize][mapSize][2];
        int cnt=0;
        int cntE=0;
 
        for(int i=0;i<mapSize;i++){
            String newStr = br.readLine();
            String[] input = newStr.split("");
 
            for(int j=0;j<mapSize;j++){
                if(input[j].equals("0")){
                    map[i][j]=0;
                }else if(input[j].equals("1")){
                    map[i][j]=1;
                }else if(input[j].equals("B")){
                    if(cnt==0){
                        if(j+1<mapSize&&input[j+1].equals("B")){
                            start = new Log(i,j+1,VERTICAL,0);
                        }else{
                            start = new Log(i+1,j,HORIZONTAL,0);
                        }
                        cnt++;
                    }
                    map[i][j]=0;
                }else{//E일
                    if(cntE==0){
                        if(j+1<mapSize&&input[j+1].equals("E")){
                            destination = new Log(i,j+1,VERTICAL,Integer.MAX_VALUE);
                        }else{
                            destination = new Log(i+1,j,HORIZONTAL,Integer.MAX_VALUE);
                        }
                        cntE++;
                    }
                    map[i][j]=0;
                }
 
            }
        }
    }
 
    static class Log{
        int row;
        int col;
        int dir; //0 가로 1 세
        int dist;
        public Log(int row, int col, int dir,int dist) {
            this.row = row;
            this.col = col;
            this.dir = dir;
            this.dist = dist;
        }
        public boolean isEnd(){
            if(this.row==destination.row && this.col == destination.col && this.dir == destination.dir)
                return true;
            return false;
        }
    }
 
 
}
 

 

문제 링크 : www.acmicpc.net/problem/1938

1938번: 통나무 옮기기