[백준, Java] 30426번, Rebirth, [DP]

문제 링크

30426번: Rebirth

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 0 ~ N-1 범위의 차원이 존재하며 처음에는 M번째 차원에 존재합니다.

2. 미아가 되는 차원은 L개가 존재하며, 해당 차원에 도착하면 더 이상 이동할 수 없습니다.

3. 문제에 대한 맞음, 틀림이 존재하며, 순서대로 풀어가며, 각 상황에 따라 G, Y만큼 차원을 이동합니다.

4. 차원을 이동할 때에는 (C + G) mod N, (C + Y) mod N으로 이동합니다.

5. 시작 차원과 M차원은 미아 차원이 될 수 없습니다.

6. 모든 문제가 끝난 뒤 0번째 차원에 가는 경우가 있으면 utopia, 가지 못하면 dystopia을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 메모이제이션과 함께 재귀를 통한 경로 탐색으로 모든 문제가 끝난 뒤 0번째 차원에 도착하는지 탐색합니다.

 

3. 탐색을 통해 0번째 차원에 갈 수 있는지에 따른 결과를 출력합니다.

 

 

차원 이동하기(DP)

 

차원을 이동하기 위해 문제를 풀 때에는 순차적으로 풀어야 합니다.

 

순차적으로 문제를 풀었을 때 중복되는 탐색이 발생할 수 있습니다.

 

만약,

 

1. 4번까지 문제를 풀었을 때 차원의 위치 : 3

 

2. 4번까지 다른 방식으로 문제를 풀었을 때 차원의 위치 : 3

 

위와 같이 이후에 탐색을 진행하면 중복되는 탐색이 발생합니다.

 

해당 중복되는 탐색에 대해서 조건(모든 문제 해결 후 0번째 차원 도착하는지)가 만족하는지 결과를 저장해서 중복되는 탐색을 방지해야 합니다.

 

DP[i][j] = i번째 문제를 풀 때 j차원일 경우

 

1 : 모든 문제를 풀고 0번째 차원이 도착 가능

 

-1 : 모든 문제를 풀어도 0번째 차원 도착 불가능

 

0 : 아직 탐색하지 않은 과정

 

위 정보를 기준으로 중복 탐색을 방지하여 모든 문제를 풀었을 때 0번째 차원에 갈 수 있는지 탐색합니다.

 

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 3

 

M = 2

 

K = 3

 

G	Y
1	2
0	1
2	1

 

2. 메모이제이션과 함께 재귀를 통한 경로 탐색으로 모든 문제가 끝난 뒤 0번째 차원에 도착하는지 탐색합니다.

 

DP[i][j] : i번째 문제를 풀 때 j차원일 경우

 

현재 차원 : 2

 

맞았을 때 → 다음 차원 : (2 + 1) % 3 = 0

 

틀렸을 때 → 다음 차원 : (2 + 2) % 3 = 1

 

 

첫 문제 맞았을 때 차원 : 0

 

맞았을 때 → 다음 차원 : (0 + 0) % 3 = 0

 

틀렸을 때 → 다음 차원 : (0 + 1) % 3 = 1

 

 

두 번째 문제 맞았을 때 차원 : 0(DP[2][0] = X)

 

맞았을 때 → 다음 차원 : (0 + 2) % 3 = 2 : X

 

틀렸을 때 → 다음 차원 : (0 + 1) % 3 = 1 : X

 

 

두 번째 문제 틀렸을 때 차원 : 1(DP[2][1] = O)

 

맞았을 때 → 다음 차원 : (1 + 2) % 3 = 0 : O

 

틀렸을 때 → 다음 차원 : (1 + 1) % 3 = 2 : X

 

 

1(O) → 2(X) → 3(O) : 순서대로 문제를 풀면 0번째 차원에 도착하는 결과를 얻었습니다.

 

 

3. 탐색을 통해 0번째 차원에 갈 수 있는지에 따른 결과를 출력합니다.

 

1(O) → 2(X) → 3(O) 경로로 문제를 풀면 조건에 만족하며, 그 결과는 DP[0][M]의 저장되어 있습니다. 

 

utopia 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해서 입력되는 차원 및 문제 정보를 띄어쓰기 기준 나누었습니다.
• 잘못된 차원에 대한 정보를 저장하였습니다.
• search함수를 통해서 문제 풀이를 진행하여 조건에 만족하는지 탐색합니다.
• 탐색을 통해 조건에 만족하면 utopia, 아니면 dystopia을 결과로 BufferdWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 문제 풀이에 대해서 재귀를 진행하여 조건에 만족하는지 탐색합니다.
• search함수는 DP[][]을 이용해서 중복 탐색을 방지하고 있습니다.

결과코드

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

public class Main {
    //move : 문제 움직임 정보 배열
    //DP : 탐색 결과 정보 배열
    static int[][] move, DP;
    //잘못된 차원 정보 배열
    static boolean[] wrongSpace;
    static int K, N;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        K =  Integer.parseInt(st.nextToken());
        move = new int[K][2];
        DP = new int[K][N];
        //문제 풀이 움직임 정보 저장
        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine()," ");
            move[i][0] = Integer.parseInt(st.nextToken());
            move[i][1] = Integer.parseInt(st.nextToken());
        }
        int L = Integer.parseInt(br.readLine());
        wrongSpace = new boolean[N];
        //잘못된 차원 정보 저장
        for(int i=0;i<L;i++){
            st = new StringTokenizer(br.readLine()," ");
            wrongSpace[Integer.parseInt(st.nextToken())] = true;
        }
        //조건에 만족하는지 탐색
        search(M, 0);
        //조건에 만족할 때
        if(DP[0][M] == 1){
            bw.write("utopia");
        }else{	//만족하지 않을 때
            bw.write("dystopia");
        }
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
    //문제 풀이를 진행하여 조건에 만족하는지 탐색하는 함수
    static int search(int position, int idx){
        //K문제를 모두 풀었을 때
        if(idx == K){
            //0번째 차원 도착할 경우
            if(position == 0){
                return 1;
            }
            //0번째 차원 도착하지 못할 경우
            return -1;
        }
        //기존에 탐색했었던 경로인 경우
        if(DP[idx][position] != 0){
            return DP[idx][position];
        }

        //맞, 틀 다음 차원 정보
        int correctNxt = (position + move[idx][0]) % N;
        int wrongNxt = (position + move[idx][1]) % N;

        //틀렸을 때 차원 이동 진행
        DP[idx][position] = wrongSpace[correctNxt] ? - 1 : search(correctNxt, idx+1);
        //조건에 만족한 경우
        if(DP[idx][position] == 1){
            return 1;
        }
        //맞았을 때 차원 이동 진행
        DP[idx][position] = wrongSpace[wrongNxt] ? - 1 : search(wrongNxt, idx+1);

        return DP[idx][position];
    }
}