[백준] 11558. The Game of Death

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://www.acmicpc.net/problem/11558

11558번: The Game of Death

---

Think🤔

문제 이해 3일 걸림..

 

첫 줄에 테스트 케이스 T 존재 [ 문제에서는 1로 나와있지만 2일 경우 두번의 결과값이 나오게 하면 됨 ]

 

 

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

public class Back11558 {
    public static void main(String[] args) throws IOException{
        try {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(bf.readLine());    // 테스트 케이스 숫자 T
            int ret = Integer.parseInt(bf.readLine());  // 플레이어 숫자, 주경이

            while(T-- > 0){
                int[] player = new int[ret+1];
                for(int i=0; i<ret; i++){
                    player[i+1] = Integer.parseInt(bf.readLine());
                }

                int point = player[1];

                int cnt = 0;
                for(int i=1; i<ret; i++){
                    if(player[i] == ret){
                        break;
                    }
                    cnt++;
                    point = player[i];
                }
                int answer = (cnt+1 == ret ? 0 : point);
                System.out.println(answer);
            }

        } catch (IOException e){
            System.out.println(e.getMessage());
        }

    }
}

이 코드의 문제점은 희현이가 주경이를 걸리게 했을 때 도달하지 못하는게 아니라 마지막에 도달할 수 있으므로
플레이어의 수와 카운트로 반복문을 다 돌게 하는 방법은 옳지 않다. 마지막에 도달하는 테스트 케이스는 다 탈락할 것
방문했을때를 체크해주는 visits을 배열로 하나 더 둬서 체크하게 해줘야 한다.

 

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

public class Back11558 {
    public static void main(String[] args) throws IOException{
        try {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(bf.readLine());    // 테스트 케이스 숫자 T

            while(T-- > 0){
                int ret = Integer.parseInt(bf.readLine());  // 플레이어 숫자, 주경이
                int[] player = new int[ret+1];
                boolean[] visits = new boolean[ret+1];

                // player[0] = 0; 배열 생성 시 0으로 초기화 하기 때문에 굳이 필요없음
                for(int i=1; i<=ret; i++){
                    player[i] = Integer.parseInt(bf.readLine());
                }

                int status = 0;
                int point = 1;
                int cnt = 0;

                while(true){
                    if(player[point] == ret){
                        cnt++;
                        break;
                    }

                    if(visits[player[point]] == true){
                        status = 1;
                        break;
                    }else{ // 첫 방문
                        point = player[point]; // 다음 방문할 곳
                        visits[point] = true;
                        cnt++;
                    }
                }
                if(status == 1){
                    System.out.println("0");
                }else{
                    System.out.println(cnt);
                }
            }

        } catch (IOException e){
            System.out.println(e.getMessage());
        }

    }
}

Status 변수 필요 없이 cnt로 제출해도 통과

물론 제출할때는 catch 부분 삭제 catch다음에 필요한 로직이 없으므로..

---

Solution✍

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

public class Main {
    public static void main(String[] args) /* throws IOException try-catch 했으므로 필요 없음 없을 시 예외를 발생시킨다 선언*/{

        try {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(bf.readLine()); 

            while(T-- > 0){
                int ret = Integer.parseInt(bf.readLine()); 
                int[] player = new int[ret+1];
                boolean[] visits = new boolean[ret+1];

                for(int i=1; i<=ret; i++){
                    player[i] = Integer.parseInt(bf.readLine());
                }

                int point = 1;
                int cnt = 0;
                
                while(true){
                    if(player[point] == ret){
                        cnt++;
                        break;
                    }

                    if(visits[player[point]] == true){
                        cnt = 0;
                        break;
                    }else{ // 첫 방문
                        point = player[point]; 
                        visits[point] = true;
                        cnt++;
                    }
                }
                System.out.println(cnt);
            }

        } 

    }
}

---

Review🤩

반복 숙달.... 실행 ....

---