백준 18235번: 지금 만나러 갑니다 (Java)

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

18235번: 지금 만나러 갑니다

 

 

 

 

 

 

 

---

 

풀이

풀이를 쓸 생각이 없었는데, 1) 왠지 모르겠는데 난이도가 골드 3이나 되길래 인터넷에 검색해보니 2) 다들 이차원 dp로 풀이를 적길래 풀이를 작성합니다.

 

1. BFS

처음 Queue에 시작점, 도착점을 넣고, 각 단계마다 visited 배열을 초기화하여 한 단계 내에서 특정 지점을 두 번 방문하면 그 단계를 정답으로 출력하면 됩니다. 이진수의 특성 상 특정 점 s에서 x단계에 e로 가는 경우의 수는 (존재한다면) 유일하기에 가능한 풀이입니다.

 

2. 거리의 차로 풀기

(구사과님 풀이를 참고했습니다.)

오리와 육리가 있는데, x일차에 두 조류들의 거리의 차는

1) 오리와 육리가 서로 같은 방향으로 이동한다: 거리 차가 줄지 않습니다.

2) 오리와 육리가 반대 방향으로 이동한다: 거리 차이가 (1<<x)만큼 줄어들거나 늘어난다.

오리와 육리의 차이를 적당히 이진수로 나타냅시다. 예제 1을 생각해보면, 두 조류의 거리차는 110입니다.

(두 오리가 만난다) <=> (거리 차가 0이 된다)이므로, 각 자리를 0으로 만들어야 합니다.

(1<<x)번째 자리가 1이라면, (1<<x)번째 자리가 0이 되려면 x번째 날에 서로 다른 방향으로 움직여야 합니다.

반대로, (1<<x)번째 자리가 이미 0이라면 x번째 날에는 서로 같은 방향으로 이동해야 합니다.

 

 

코드

풀이 1

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        if ((A-B) % 2 == 1) {
            System.out.println(-1);
            return;
        }
        
        int dist = 1;
        int day = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(A);
        queue.offer(B);
        
        while (!queue.isEmpty()) {
            day++;
            int size = queue.size();
            boolean[] visited = new boolean[N+1];
            while (size-- > 0) {
                int cur = queue.poll();
                int nxt = cur + dist;
                if (nxt <= N) {
                    if (visited[nxt]) {
                        System.out.println(day);
                        return;
                    }
                    visited[nxt] = true;
                    queue.offer(nxt);
                }
                nxt = cur - dist;
                if (nxt > 0) {
                    if (visited[nxt]) {
                        System.out.println(day);
                        return;
                    }
                    visited[nxt] = true;
                    queue.offer(nxt);
                }
            }            
            dist *= 2;
        }
        System.out.println(-1);
    }
 
}
 

 

 

풀이 2

import java.io.*;
import java.util.*;
 
// 구사과님 풀이 참고함
public class Main {
 
    static int ans = 100, N;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        if ((A-B) % 2 == 1) {
            System.out.println(-1);
            return;
        }
        
        dfs(A, B, 0);
        System.out.println((ans == 100)? -1: ans);
    }
 
    static void dfs(int s, int e, int d) {
        if (s <= 0 || s > N || e <= 0 || e > N) return;
        
        if (s == e) {
            ans = Math.min(ans, d);
            return;
        }
        
        if (Math.abs(s-e) % (4 << d) == (2 << d)) {
            dfs(s + (1<<d), e - (1<<d), d+1);
            dfs(s - (1<<d), e + (1<<d), d+1);
        } else {
            dfs(s + (1<<d), e + (1<<d), d+1);
            dfs(s - (1<<d), e - (1<<d), d+1);
        }
        
    }
}