본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[백준 BAEKJOON 알고리즘] 주사위 굴리기- 14499번 문제 풀이 및 해설

백준 baekjoon 알고리즘

알고리즘 분류: 시뮬레이션

[14499] 주사위 굴리기

----------------------------------------------------------------------------------------------------

문제

크기가 N*M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위 하나가 놓여져 있으며, 주사위의 전개도는 아래와 같다.

지도의 좌표는 (r,c)로 나타내며, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 

주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x,y)이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다. 지도의 각 칸에는 정수가 하나씩 쓰여져 있다.

주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 된다.

주사위를 놓은 곳의 좌표와 이동시키는 명령이 주어졌을 때, 주사위가 이동했을 때마다 상단에 쓰여 있는 값을 구하는 프로그램을 작성하시오.

주사위는 지도의 바깥으로 이동시킬 수 없다. 만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도 하면 안된다.

입력

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1<=N, M<=20), 주사위를 놓은 곳의 좌표 x y (0<=x<=N-1, 0<=y<=M-1), 그리고 명령의 개수 K(1<=K<=1000)가 주어진다.

둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수이다.

마지막 줄에는 이동하는 명령이 순서대로 주어진다. 동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4로 주어진다.

출력

이동할 때마다 주사위의 윗 면에 쓰여 있는 수를 출력한다. 만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도 하면 안된다.

예제

입력 출력

4 2 0 0 8 

0 2

3 4

5 6

7 8

4 4 4 1 3 3 3 2

0

0

3

0

0

8

6

3

3 3 1 1 9

1 2 3

4 0 5

6 7 8

1 3 2 2 4 4 1 1 3

0

0

0

3

0

1

0

6

0

2 2 0 0 16

0 2

3 4

4 4 4 4 1 1 1 1 3 3 3 3 2 2 2 2

0

0

0

0

3 3 0 0 16

0 1 2

3 4 5

6 7 8

4 4 1 1 3 3 2 2 4 4 1 1 3 3 2 2

0

0

0

6

0

8

0

2

0

8

0

2

0

8

0

2

 

 

풀이

문제도 길고 예제도 기네요 ㅎㅎ (참고로 답지만 필요하신 분은 내리다보면 빨간색 글씨로 전체코드 써놓은 부문만 보세요 ㅎㅎ)

핵심만 정리를 먼저 해보자면

 

###정리###

 

지도: N*M 

지도좌표 : (r,c) r:위부터 기준 c 왼쪽부터 기준

주사위 초기화: 시작점: 0, 시작 좌표(x,y)

주사위 윗면: 1 왼면 : 3

동쪽1 서쪽2 북쪽3 남쪽4

 

조건

이동한 칸에 쓰여있는 수가 0? -> 바닥면 수가 칸에 복사

0이 아닌 경우? ->주사위 바닥면 값 = 칸 안의 수 

 

입력

1라인: 지도 세로, 지도 가로, 주사위 시작 좌표 x, 주사위 시작 좌표 y, 명령의 개수 k 

2라인: (주사위를 놓은 칸 수는 항상 0)

지도에 쓰여 있는 수

마지막 라인: 이동 명령

 

출력

each 이동 명령 수행, 상단 값 

예외: 지도의 바깥ㅇ -> 무시 , 출력 x

########

 

정리를 하면 나중에 조건을 찾기도 쉽고 문제를 이해하기도 쉬워요.

시간이 없으면 이렇게 정갈하게 정리를 하지는 못하지만, 긴 문제의 경우 저는 정리해주는 편입니다.

일단 제가 푼 흐름의 순서대로 설명을 해볼게요 

 

잠깐?! 이 문제에서 주의해야할 점과 짜증나는 점이 있어요 

 

1. 행과 열, x축과 y축 잘 잡고 가기

먼저 행렬을 한 번 정리하고 갈게요 

 

N*M에서 앞에 N은 행, 즉 좌표로 따지면 y축에 해당합니다.

뒤에 M은 열! 즉 좌표로 따지면 x축에 해당해요. (x축은 좌우 이동에 따라서 값이 변하니까 열이 변할 때 영향을 받잖아요)

N*M이니까 단순히 (x,y)라고 생각해서 실수하시는 분들이 많습니다.

즉 x표는 열에 해당합니다.

 

 

2. 문제 해석 잘하기

혹 저처럼 잘못 해석한 사람도 있나요?

아..아무리 풀어도 분명 맞는데 왜 답이 안나오지 했는데...

"주사위는 지도 위에 윗 면이 1이고 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며"라고 문제에서 언급해서

주사위 윗면에 1이 적혀있고 동쪽면에 3이라는 숫자가 적혀있다는 얘긴줄 알았는데..

그냥 주사위 윗면을 배열할때 기준을 1로 잡으라는거였어.. 이거 저처럼 오해하신 분들 없나요? 정말 시간 낭비..  진짜 시간 낭비 오지게했네요 ㅠㅠ 그림이 있었는데 그림을 제대로 안보고...ㅠㅠ 글만 읽으니까 말이 애매해서 저렇게 이해해버렸네요 ㅎㅎ 꼼꼼히 읽고 이해합시다

1
int[] dice = new int[] {0,0,0,3,0,1}; //바텀, 왼, 정면, 오, 뒤, 탑
cs

내 코드에서 이거 그냥 싸그리 다 0으로 초기화해주기만 하면 해결되는거였음 ㅠ 저는 윗면이 1이라는 값을 가지고 있다는 줄.. 아까운 시간..밍

 

[Java]

오늘은 자바 먼저~ 사실 저 명확하지 않은 문장 때문에 시간낭비를 너무 해서 C++까지 작성할 기력이 있을지 ㅠㅠ

(그림의 숫자를 간과하고 문장만 열시미 읽은 멍청이)

일단 처음부터 다시 차례차례 봅시당

먼저 주사위와 지도 초기화를 해줘야겠죠? 

그리고 보면 명령 개수와 출력개수가 달라요. 아마 지도 밖으로 내보내는 명령은 무시돼서 그럴거예요. 이거 다 빼고 시작하게 예외처리 먼저 해주고 갈게요

@import.util.Scanner;
public Class Main{
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int k = sc.nextInt();
 
        int[][] map = new int[N][M];
        for(int row =0; row<N; row++){
            for(int col =0; col<M; col++){
                map[row][col] = sc.nextInt();
            }
        }
        int dir;
        while(k>0){
            dir = sc.nextInt();
            //방향에 따라 (x,y) 한 칸 움직이기
            //새로운 위치가 지도에서 벗어날 경우 무시
 
            //명령 수행 후 주사위 상단 값 구하기
            k--;
        }
    }
}

여기까지는 입출력받는거라 다 하셨을거예요

아무래도 입력을 반복문으로 받기 때문에 시간을 좀 줄여주고 싶다 하시는 분들은 or 시간초과 나시는 분들은

이 부분을 BufferedReader을 사용해서 구현하면 됩니다. 하는 김에 변수들까지 멤버변수로 싹 빼서 정리해줬어요 ↓

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
public class Main {
    private static int[][] map;
    private static int N;
    private static int M;
    private static int x;
    private static int y;
    private static int k;
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());
       N = Integer.parseInt(st.nextToken());
       M = Integer.parseInt(st.nextToken());
       x = Integer.parseInt(st.nextToken());
       y = Integer.parseInt(st.nextToken());
       k = Integer.parseInt(st.nextToken());
       
       map = new int[N][M];
       for(int r=0; r<N; r++) {
           st = new StringTokenizer(br.readLine());
           for(int c=0; c<M; c++) {
               map[r][c] = Integer.parseInt(st.nextToken());
           }
       }
       
       st=new StringTokenizer(br.readLine());
       while(k>0) {
           int dir = Integer.parseInt(br.readLine());
           //지도에서 방향으로 움직이기
           //위치가 벗어낫는지 확인
           //명령 수행 후 주사위 상단 값 구하기
             k--;
       }
    }
}

이제 이동했을 때 좌표를 구하는 로직을 생각해봅시당. 현재 좌표는 x,y예요 

여기서 동쪽 서쪽이 들어올 경우, x좌표에 영향이 갈꺼고 북쪽 남쪽이 들어올 경우 y에 영향이 갈꺼예요

"동 서 북 남"이 "1 2 3 4"이므로 동쪽은 오른쪽, 서쪽은 왼쪽, 북쪽은 위쪽, 남쪽은 아래쪽이잖아요

동쪽으로 움직이면 +1이겠죠?. 왜냐 조건을 보면 (r,c)의 r은 왼쪽을 기준으로 세기 때문에 오른쪽으로 갈수록 플러스가 돼요 즉 서쪽으로 가야 r이 -1이 됩니다. 북쪽도 마찬가지예요. 똑같이 생각해주셔야 합니다. 그런데 북쪽은 위로 올라간다는 느낌이 있어서 그런가 아무래도 우리가 수학 x,y좌표 배울때는 위가 플러스이니까요 ㅎㅎ 즉 북쪽으로 간다고 해서 +1이 아닙니다. 왜냐 조건을 보면 (r,c)에서 c는 위를 기준으로 세기 때문에 내려갈수록 플러스가 돼요. 북쪽으로 가면 -1이다. 

즉 동서북남은 각 [x-1, x+1,y -1,y +1] 영향을 줍니다. x와 y좌표 나눠서 생각해주면  아래처럼 될거예요.

import java.util.Scanner;
import java.io.IOException;
public class Main {
    public static void main(String[] args) throws IOException {
        
        //위코드와 동일하므로 여기는 생략
        int dir; 
        int[] xdir = new int[] {+1,-1,0,0};
        int[] ydir = new int[] {0,0,-1,+1};
        int nx, ny;
        while(k>0) {
            dir = sc.nextInt();
            nx = x+ xdir[dir-1];
            ny = y+ ydir[dir-1];
            
            if(nx>=0 && nx< M && ny>=0 && ny< N)
            {
                //다이스를 굴려요 
                x=nx; y=ny;
                if(map[x][y] == 0) {
                    map[x][y] = 다이스 바닥면; 
                }else {
                    다이스 바닥면 = map[x][y]; map[x][y]=0;
                }
                System.out.println(다이스 상단 값);
            }
            k--;
        }
    }
}

이렇게 하셨으면 벌써 실수하신 겁니다. ㅎㅎ아까 x가 열을 의미한다고 했잖아요?!

n,m <-> x,y 이렇게 생각해서 n(행)이 x와 관련있다고 무의식 중에 저기 조건문을 잘못 작성해주는 친구들이 있어요. 에러가 났다면 이것 때문은 아닌지 한 번 확인해줍시다. 20라인에서 인덱스아웃오브바운드 오류가 뜰거예요. map[x][y]에서 x는 행을 가리키는 라니니까요 ㅎㅎ

물론map[y][x]이렇게 고쳐서 써줘도 되지만 그럼 코드 해석하기가 너무 어렵지않나요

 

행렬좌표와 우리가 일반적으로 배웠던 직교좌표계는 기준이 다릅니다. 혼동해서 쓰려하지마시구

동서남북 문제 풀때는 직교좌표계를 생각하지 말고 정의를 새로 내리는게 안헷갈려요 

x를 좌표계의 그 x말고 그냥 매개변수 x로 생각해야 해요. map[N][M] , map[x][y]이렇게 쓸 수 있게 x를 0과 N사이의 변수 즉 행 변수로 정의를 하고 갈게요 

package justTest;
 
import java.util.Scanner;
import java.io.IOException;
public class Main {
    
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();        
        int x = sc.nextInt();
        int y = sc.nextInt();
        int k = sc.nextInt();
    
        int[][] map = new int[N][M];
        for(int r = 0; r<N; r++) {
            for(int c =0; c<M; c++) {
                map[r][c]=sc.nextInt();
            }
        }
        int[] xdir = {0,0,-1,1};
        int[] ydir = {1,-1,0,0};
        int dir; 
    
        int nx, ny;
        while(k>0) {
            dir = sc.nextInt();
            nx = x+ xdir[dir-1];
            ny = y+ ydir[dir-1];
           
            if(nx>=0 && nx< N && ny>=0 && ny< M)
            {
                //주사위 굴리기
                 x=nx; y=ny;
                 if(map[x][y] == 0) {
                     map[x][y] = 주사위 바닥; 
                 }else {
                     주사위 바닥 = map[x][y];
                     map[row][col]=0;
                 }
                 System.out.println(다이스 상단 값);
            }
            k--;
        }
    }
}

그러므로 동쪽을 오른쪽으로 갔다는 건 열이 변한 것이기 때문에 행을 뜻하는 x+1이 아니라 y+1이 되야합니다.

그래서 int ydir = {1,-1,0,0}이 되는거예요 

자꾸 x가 헷갈리시면 아예 변수명을 다르게 지어도 됩니다. 아래 코드는 헷갈리지 않게 변수명을 바꿨어요. 멤버변수로 다 빼서 작성하는게 좋지만 해설하는데 코드가 자꾸 길어지는거같아서 이렇게 작성할게요 (BufferdReader로 입력받은 코드 참고하기!)

import java.util.Scanner;
import java.io.IOException;
public class Main {
    
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();        
        int row = sc.nextInt();
        int col = sc.nextInt();
        int k = sc.nextInt();
        
        int[][] map = new int[N][M];
        for(int r = 0; r<N; r++) {
            for(int c =0; c<M; c++) {
                map[r][c]=sc.nextInt();
            }
        }
        
        int dir; 
        //행은 남쪽 북쪽으로 움직일 때 관련있음
        int[] drow = new int[] {0,0,-1,+1}; 
        int[] dcol = new int[] {1,-1,0,0}; 
        
        int nrow, ncol;
        while(k>0) {
            dir = sc.nextInt();
            nrow = row+ drow[dir-1];
            ncol = col+ dcol[dir-1];
      
            if(nrow>=0 && nrow< N && ncol>=0 && ncol< M)
            {
                //주사위 굴리기
                 row=nrow; col=ncol;
                 if(map[row][col] == 0) {
                     map[row][col] = 주사위 바닥면; 
                 }else {
                     주사위 바닥면 = map[row][col];
                     map[row][col]=0;
                 }
                 System.out.println(다이스 상단 값);
            }
            k--;
        }
    }
}

주사위를 정의해줘야 한다 그래놓고 주사위 정의가 빠졌네요 주사위를 정의해줍시다. 저는 문제에서 주사위는 지도 위에 윗 면이 1이고 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며" 를 면이 가지고 있는 값으로 잘못 해석해서

그냥 내 맴대로 순서를 정해서 주사위를 정의해서 풀었었어요. 원래 다른 방법으로 한 문제를 여러번 푸는 데 아 저거때문에 기가 너무 다 빨렸ㅇ.....

 int[] dice = new int[6];  6면이니까 요렇게? 면 규칙도 그냥 - 밑면, 왼쪽면, 앞면, 오른쪽면, 뒷면, 윗면 이렇게 정의했습니다. 이렇게 문제 풀어도 답은 맞기 때문에 상관없어요. 하지만 문제에서 윗면을 1로 기준잡아서 나열해달라니까 문제가 요구하는대로 풀어볼게요

 

저 전개도 사진이 알려주는거처럼 

이렇게 순서를 잡도록 하겠습니다.

1 - 윗면

2 - 뒷면

3 - 오른쪽면

4 - 왼쪽면

5 - 앞면

6 - 밑면

1로 기준을 해달라했으니 면은 6개지만 0index는 없는 것처럼 생각하고 1,2,3,4,5,6을 각 인덱스로 사용할 수 있게 7개의 공간으로 주사위를 잡을게요

--> int[] dice=new int[7];

 

//주사위 굴리기 부문을 작성해봅시다. 메소드로 빼줘도 되고 그냥 메인에다가 쭉 작성해줘도 됩니다

if(k==1){
    동쪽으로 굴림
    주사위를 오른쪽으로 굴리면 왼쪽에 있던게 들어옴
    즉 윗면에는 왼쪽면 값이 들어간다.
    욋면 = 왼쪽면 값
    왼쪽면 값 = 밑면 값 등등..
}else if(k==2){
    서쪽으로 굴림
    마찬가지로 왼쪽으로 굴렸으니 오른쪽에 있던게 나한테 들어옴
    윗면에는 오른쪽 값이 들어온다
    윗면 = 오른쪽면 값
}else if(k==3){
    북쪽으로 굴림 즉 뒤로 굴림
    윗면 = 앞면 값
}else {
    남쪽으로 굴림
    윗면 = 뒷면 값
    요런 규칙 
}
 

규칙에 따라서 작성하면 전체 코드는 아래와 같습니다.

<전체 코드>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
public class Main {
     private static int[][] map;
     private static int N;
     private static int M;
     private static int row;
     private static int col;
     private static int k;
     public static void main(String[] args) throws IOException {
         // TODO Auto-generated method stub
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());
       N = Integer.parseInt(st.nextToken());
       M = Integer.parseInt(st.nextToken());
       row = Integer.parseInt(st.nextToken());
       col = Integer.parseInt(st.nextToken());
       k = Integer.parseInt(st.nextToken());
        
       map = new int[N][M];
       for(int r=0; r<N; r++) {
           st = new StringTokenizer(br.readLine());
           for(int c=0; c<M; c++) {
               map[r][c] = Integer.parseInt(st.nextToken());
           }
       }
        //행은 남쪽 북쪽으로 움직일 때 관련있음
        int[] drow = new int[] {0,0,-1,+1}; 
        int[] dcol = new int[] {1,-1,0,0};
        int[] dice = new int[7]; 
    
        int nrow, ncol;
         st = new StringTokenizer(br.readLine());
        while(k>0) {
            int dir = Integer.parseInt(st.nextToken());
            nrow = row+ drow[dir-1];
            ncol = col+ dcol[dir-1];
           
            if(nrow>=0 && nrow< N && ncol>=0 && ncol< M)
            {
                int top = dice[1];
                 if(dir == 1) { //동쪽  탑이 오른쪽으로 감
                     dice[1] =dice[4]; //탑 = 왼쪽
                     dice[4]=dice[6];
                     dice[6]=dice[3];
                     dice[3]=top;
                 }else if(dir ==2) { 
                     dice[1]=dice[3]; 
                     dice[3]=dice[6];
                     dice[6]=dice[4];
                     dice[4]=top;
                 }else if (dir ==3) {//북쪽  탑이 위쪽으로감 
                     dice[1] =dice[5];
                     dice[5]=dice[6];
                     dice[6]=dice[2];
                     dice[2]=top;
                     
                 }else{ //입력값이 1~4까지만 들어온다는 가정하에 
                     dice[1]=dice[2];
                     dice[2]=dice[6];
                     dice[6]=dice[5];
                     dice[5]=top;        
                 } 
                 row=nrow; col=ncol;
                 if(map[row][col] == 0) {
                     map[row][col] = dice[6]; 
                 }else {
                     dice[6] = map[row][col];
                     map[row][col]=0;
                 }
                 System.out.println(dice[1]);
            }
            k--;
        }
    }
}

메모리: 13956KB

시간: 120ms

코드길이 2764B

 

오늘은 조금 풀이가 긴 포스팅이였죠?! ㅎㅎ C/C++언어는 풀이가 너무 긴 관계로 다른 포스팅으로 빼서 다루도록 할게요!

모두 수고하셨어요 ㅎㅎ 댓글, 공감, 광고보답 등은 질 좋은 포스팅 공유에 힘이 됩니다. 헿

  • 감사왕김감사 2019.12.29 22:24

    문제 해석 잘못하고 출력이 왜 저렇게 나오는지 한참 고민하다가 본 포스트 읽고 해결했네요 ㅜㅜ

    • IT 양햄찌(jhnyang) 2020.01.04 14:58 신고

      핳 저랑 초반에 동일하게 문제 해석 잘못했군요 ㅎㅎ코딩어려운거보다 문제 애매해서 해메는게 더 고생스럽죠 ㅠ ㅎ 포스팅을 해놔서 다행이예요. :)