[백준] 13549 : 숨바꼭질 3 (JAVA/자바)

문제

BOJ 13549 : 숨바꼭질 3 - https://www.acmicpc.net/problem/13549

풀이

저번에 풀어봤던 숨바꼭질 문제에서 순간이동의 time 조건만 바뀐 문제였다. BFS로 풀이하는데, 3가지 경우 모두 time이 1만큼 증가되는 경우는 단순히 visited 처리만 해서 이미 방문한 적이 있는 위치면 큐에 넣지 않는 방식으로 풀이했었다.

하지만 이 문제의 경우, 특정 위치를 방문한 적이 있더라도 순간 이동으로 time 증가 없이 이동할 경우 시간이 더 빠르게 방문할 수 있기 때문에 visited를 boolean이 아닌 int로 선언하여 몇 time에 도달했는지를 저장해주었다.

특정 위치에 방문 했을 때, 1) 여태까지 방문한 적이 없거나 2) 이미 방문한 적이 있지만 방문된 time이 지금 time+1보다 크다면 다시 방문처리를 해주었다!

그리고 또 하나, 일반적인 BFS는 목표 위치에 도달하는 순간 BFS를 종료해도 됐지만 이번 문제의 경우 먼저 방문한다고 time이 적은게 아니기 때문에 목표 지점에 도달하는 순간 결과를 print하면 틀렸습니다가 뜬다~

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static class Loc{
        int idx;
        int time;

        public Loc(int idx, int time) {
            this.idx = idx;
            this.time = time;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int n = Integer.parseInt(inputs[0]); // 수빈이의 위치
        int k = Integer.parseInt(inputs[1]); // 동생의 위치

        int[]  visited = new int[100001];

        Queue<Loc> q = new LinkedList<>(); // location(위치) 저장
        q.add(new Loc(n, 1)); // 시작 time을 1로 해놓고, 결과 출력시 1 빼기. visited의 값이 0인 것(방문 안한 곳)과 구별해주기 위해서.
        visited[n] = 1; 

        while (!q.isEmpty()) {
            Loc now = q.poll();
            
            // 이렇게 쓰면 틀림
//            if(now.idx==k) {
//                visited[now.idx] = now.time;
//                System.out.println(now.time-1);
//                break;
//            }

            if(now.idx+1>=0 && now.idx+1<=100000){ // 앞으로 한칸
                if(visited[now.idx+1] == 0 || visited[now.idx+1] > now.time+1){
                    visited[now.idx+1] = now.time+1;
                    q.add(new Loc(now.idx + 1, now.time + 1));
                }
            }

            if(now.idx-1>=0 && now.idx-1<=100000){ // 뒤로 한칸
                if(visited[now.idx-1] == 0 || visited[now.idx-1] > now.time+1) {
                    visited[now.idx - 1] = now.time + 1;
                    q.add(new Loc(now.idx - 1, now.time + 1));
                }
            }

            if(now.idx*2>=0 && now.idx*2<=100000){ // 순간이동
                if(visited[now.idx*2] == 0 || visited[now.idx*2] > now.time) {
                    visited[now.idx*2] = now.time;
                    q.add(new Loc(now.idx*2, now.time));
                }
            }

        }

        System.out.println(visited[k]-1);



    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 너비 우선 탐색, 다익스트라, 0-1 너비 우선 탐색
✔ 난이도 - 🟡 Gold 5

🤦‍♀️ 오늘의 메모

• 사실 정답률이 낮은 문제이길래 조금 쫄아서 제출했는데 너무 쉽게 맞았습니다가 떴다. 이게 되네 싶어서 다른 블로그들을 찾아봤더니 가중치가 동일하지 않은 정점을 이동하기 때문에 Q에 넣는 순서를 *2 -> -1 -> 1 순서로 한다면 단순 방문처리(True/False)로도 풀 수 있다고 한다! 조금 복잡하게 푼 것 같지만 가중치가 다른 경우를 고려하는 방법에 대해 생각해볼 수 있던 문제였던 것 같다.

참고 사이트

딱히 없음