[BOJ] #17836 공주님을 구해라, #14499 주사위 굴리기, #9375 패션왕 신해빈(java)

#17826 공주님을 구해라

문제로가기

문제이해

용사에서 공주까지 갈 때 최단 거리를 구해야한다.

용사은 상하좌우 이동할 수 있다.

벽은 이동할 수 없다. 빈칸만 이동할 수 있다.

1칸당 이동하는데 1시간이 소요된다. T 시간이 넘어가면 fail을 출력해야 한다.

* 조건 * 그람 위치에서 그람을 만나면 벽도 이동이 가능한다.

 

 

 

해결 방법 고안

1. 최단거리 임으로 bfs를 이용한다.

2. 검의 위치에 도달하면 que를 사용하지 않고 바로 그 거리에서 공주까지의 직선 거리를 구한다.

 

약간의 삽질

처음에 검이 위치까지 가기전에 거리를 구했고, 검의 위치에서 다시 que를 사용해서 최단거리를 구하려고 했다.

그럴 필요 없이 그냥 검의 위치에서 직선방향으로 (x , y)에서 공주의 위치 ( n-1, m-1)를 구하면 됐었다.

 

코멘트

조건을 잘 확인하고 코드를 작성하자. 조건 확인을 안했어서 계속 틀리다고 나와서 삽질을 좀 했는데

처음부터 조건을 확인하고 코드를 짰으면 시간 단축이 훨씬 되었을 듯 하다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Boj공주님을구해라 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    private static StringBuilder output = new StringBuilder();
    private static int map[][];
    private static boolean visited[][];
    private static int deltas[][] = {{1,0},{0,1},{-1,0},{0,-1}};
    private static int n,m,t,res, gamRes;
    private static boolean flag;
    private static int gam[];
    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        n = Integer.parseInt(tokens.nextToken());
        m = Integer.parseInt(tokens.nextToken());
        t = Integer.parseInt(tokens.nextToken());
        gam = new int[2];
        map = new int[n][m];
        visited = new boolean[n][m];

        for(int i=0; i<n; i++){
            tokens = new StringTokenizer(input.readLine());
            for(int j=0; j<m; j++){
                map[i][j] = Integer.parseInt(tokens.nextToken());
                if(map[i][j]==2){
                    gam[0] =i;
                    gam[1]=j;
                }
            }
        }
        bfs();
        if(flag && map[n-1][m-1]==-1)  {
            res = Math.min(res, gamRes);
            System.out.println(res);
        }
        else System.out.print("Fail");
    }
    private static void bfs(){
        flag  =true;
        Queue<int []> que = new LinkedList<>();
        que.offer(new int[] {0,0,0});
        visited[0][0] = true;
        while(!que.isEmpty()){
            int temp[] = que.poll();
            int x = temp[0];
            int y = temp[1];
            int cnt = temp[2];
            //시간넘으면 바로 종료
            if(cnt > t){
                if(gamRes == 0){
                    flag  =false;
                }
                break;
            }
            //도착하면 멈추기
            if(x == n-1 && y==m-1){
                res = cnt;
                map[n-1][m-1]=-1; //도달한 경우 -1로 바꿔놓기
                break;
            }
            //검이라면
            if(x == gam[0] && y == gam[1]){
                int distance =  (n-1 -x) + (m-1-y);
                 gamRes= cnt+distance;
                if(gamRes > t){
                    flag = false;
                    break;
                }
            }
            for(int d[]:deltas){
                int nx = x+d[0];
                int ny = y+d[1];
                if(nx >=0 && nx<n && ny>=0 && ny<m){
                    if(!visited[nx][ny]){ //방문하지 않았고 벽이 아니여야함
                        if(map[nx][ny]!=1){
                            que.offer(new int[] {nx,ny,cnt+1});
                            visited[nx][ny] = true;
                        }
                    }
                }
            }
        }

    }
}

 

 

 

#14499 주사위  굴리기

문제로가기

문제이해

주사위와 지도가 있다.

주사위를 굴려서 지도를 이동하게 된다

주사위가 최종으로 지도를 이동하면서 바뀌게 되는 주사위의 윗면을 출력한다.

 

 

해결 방법 고안

1. 주사위 좌표 이동

동서남북 별로 위에 적은 것처럼 우선 주사위를 굴릴 때마다 바뀌게 되는 주사위의 좌표를 저장해야 한다.

우선 나같은 경우는  dice배열을 선언하고 아래처럼 인덱스를 저장해놓았다.

dice[0]윗면, dice[1]왼쪽, dice[2]바닥!!, dice[3]오른쪽 , dice[4]앞면, dice[5]뒷면

 

그리고 시뮬레이션을 돌려서 동, 서, 남, 북 별로 주사위가 이동될 때 바뀌게 되는 배열을 저장했다.

 

2. 지도에 도착했을 때 결정

지도의 범위를 벗어나지 않는 한에서 지도에 도착했을 때 좌표가 0이면 주사위의 아랫면을 복사하고

0이 아니라면 주사위의 아랫면에 복사되고 0으로 바뀐다

if(map[nx][ny] == 0){ //칸이 0이라면
    map[nx][ny] = dice[2]; //바닥면에 있는 수가 복사
}
else{
    dice[2] = map[nx][ny]; //칸에 있는 수가 복사
    map[nx][ny] = 0;
}

 

코멘트

주사위 배열이 바뀔 때 배열밀기, 돌리기 등 복잡하게 생각했는데 그냥 빡구현 문제였다

의외로 간단(?)

 

전체코드

import java.io.*;
import java.util.*;

// 14844 kb
// 136 ms

public class Boj주사위굴리기 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    private static StringBuilder output = new StringBuilder();
    private static int n,m,x,y,k;
    private static int map[][];
    private static int [] kArr, dice;
    public static void main(String[] args) throws IOException {
        dice = new int[6];
        tokens = new StringTokenizer(input.readLine());
        n = Integer.parseInt(tokens.nextToken());
        m = Integer.parseInt(tokens.nextToken());
        x = Integer.parseInt(tokens.nextToken());
        y = Integer.parseInt(tokens.nextToken());
        k = Integer.parseInt(tokens.nextToken());

        map = new int[n][m];
        for(int i=0; i<n; i++){
            tokens = new StringTokenizer(input.readLine());
            for(int j=0; j<m; j++){
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }
        kArr = new int[k];
        tokens = new StringTokenizer(input.readLine());
        for(int i=0; i<k; i++){
            kArr[i] = Integer.parseInt(tokens.nextToken());
        }
        for(int c : kArr){
            rotate(c);
        }
    }
    //주사위
    //dice[0]윗면, dice[1]왼쪽, dice[2]바닥!!, dice[3]오른쪽 , dice[4]앞면, dice[5]뒷면
    private static void rotate(int command){
        boolean flag = false;
        int nx = x;
        int ny = y;
        switch(command){
            case 1: //동쪽
                if(ny+1 <m){
                    flag = true;
                    ny = ny+1;
                    //뒷면 앞면은 그대로
                    int temp = dice[0];
                    dice[0] = dice[1]; //왼쪽이 위로 올라옴
                    dice[1] = dice[2];
                    dice[2] = dice[3];
                    dice[3] = temp;
                }
                break;
            case 2: //서쪽으로
                if(ny-1>=0){
                    flag = true;
                    ny = ny-1;
                    int temp = dice[0];
                    dice[0] = dice[3];
                    dice[3] = dice[2];
                    dice[2] = dice[1];
                    dice[1] = temp;
                }
                break;
            case 3: // 북쪽
                if(nx-1 >=0){
                    flag = true;
                    nx = nx-1;
                    int temp = dice[0];
                    dice[0]=dice[4];
                    dice[4]=dice[2];
                    dice[2]=dice[5];
                    dice[5]=temp;
                }
                break;
            case 4: //남쪽
                if(nx+1 < n){
                    flag = true;
                    nx = nx+1; //주사위 이동
                    int temp = dice[0];
                    dice[0]=dice[5];
                    dice[5]=dice[2];
                    dice[2]=dice[4];
                    dice[4]=temp;
                }
                break;
        }
        if(flag){
            x = nx;
            y = ny;
            if(map[nx][ny] == 0){ //칸이 0이라면
                map[nx][ny] = dice[2]; //바닥면에 있는 수가 복사
            }
            else{
                dice[2] = map[nx][ny]; //칸에 있는 수가 복사
                map[nx][ny] = 0;
            }
            System.out.println(dice[0]);
        }
    }
}

 

 

#9375 패션왕 신혜빈

문제보러가기

문제 이해

옷을 조합으로 입는다. 단, 한번 입은 옷은 입으면 안된다. 아무것도 안입어서도 안된다.

 

해결 방법 고안

첫 번째 시도

문제에서도 조합으로 주어져서 조합으로 가능한 수를 다 구하고, 겹치는 옷의 종류와 아무것도 입지 않았을 때를 빼주었는데 메모리 초과가 나서 실패했다. 2^N 임으로 N이 커져버리면 메모리 초과가 나는 문제였다.

 

두 번째 시도

hashmap을 사용해서 같은 종류가 몇개 있는지 파악한다.

같은 종류에서 ex) headgear가 2개이고 name은 hat, turban 일때 가능한 수는 {hat}, {turban}, {null}이다.

null을 넣어주고 나중에 1를 빼면 되는 것이다.

 

알게된 점

hashmap 메소드를 공부하는 계기..

getOrDefault

getorDerfaults(key, default)이렇게 사용하면 된다. key값이 있을 때는 value값이 나오게 되고 없으면 default값이 나온다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Boj패션왕신해빈 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    private static StringBuilder output = new StringBuilder();
    private static int n;
    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(input.readLine());

        for(int t=0; t<T; t++){
            HashMap<String, Integer> map = new HashMap<>();
            n =Integer.parseInt(input.readLine());
            for(int i=0; i<n; i++){
                tokens = new StringTokenizer(input.readLine());
                String name = tokens.nextToken();
                String type = tokens.nextToken();
                map.put(type, map.getOrDefault(type, 0)+1);
            }
            int result=1;
            for(int cnt : map.values()){
                result *=(cnt+1);
            }
            System.out.println(result-1);
        }
    }
}