[JAVA] BOJ 백준 1194번 - 달이 차오른다, 가자.

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1194번: 달이 차오른다, 가자.

---

2. 내가 푼 방법

비트 연산자를 이용해 풀면 훨씬 코드가 간단해지는 문제이다.

• | 연산 : OR 연산자로, 피연산자 중 한쪽 값이 1일 경우에 1을 반환하고, 그 외에는 0을 반환한다.
• & 연산 : AND 연산자로, 피연산자 양 쪽 값이 모두 1일 경우에 1을 반환하고, 그 외에는 0을 반환한다.
• ^ 연산 : XOR 연산자로, 두 개의 피연산자 값이 다를 때 1을 반환하고, 같을 때에는 0을 반환한다.
• << 연산 : x << y, 정수 x의 각 비트 값을 y만큼 이동시킨다. (빈자리는 0으로 채워짐) (ex. 1 << 2 = 10)

 

먼저, 키를 이용할 때 비트 연산자를 통해 표현한다. 'a'는 0만큼의 쉬프트 연산, 'b'는 1만큼의 쉬프트 연산을 하는데, 결국 키 'a'를 가지고 있을 경우 1, 키 'b'를 가지고 있을 경우 10, 키 'c'를 가지고 있을 경우 100으로 표현될 수 있다.

 

따라서 다음 위치가 문이면 키와 다음 위치를 쉬프트 연산한 값이 모두 1이어야 하므로 AND(&) 연산을 해준다. 1을 반환한 결과값 임과 동시에 현재 키 리스트를 가지고 방문한 적 없는 위치일 경우에만 다음 위치로 넘어갈 수 있다. 그리고 만약 다음 위치가 키라면 OR(|) 연산을 통해 키를 업데이트하면서 현재 키 리스트를 가지고 방문했음을 업데이트해준다.

public static void dfs(int x, int y, int cnt, int key) {
    if (arr[x][y] == '1') {
        result = Math.min(result, cnt);
        return;
    }

    if (Character.isLowerCase(arr[x][y])) {
        if ((key & (1 << arr[x][y] - 'a')) == 0) {
            key |= 1 << arr[x][y] - 'a';
        }
    }

    visit[x][y][key] = cnt;

    for (int i = 0; i < dx.length; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (arr[nx][ny] == '#' || (visit[nx][ny][key] != null && visit[nx][ny][key] <= cnt + 1)) continue;

        if (Character.isUpperCase(arr[nx][ny])) {
            if ((key & (1 << arr[nx][ny] - 'a')) == 0) continue;
        }

        dfs(nx, ny, cnt + 1, key);
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1194.java

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

class Main {
    static int N, M;
    static char[][] arr;
    static Integer[][][] visit;
    static int sx, sy;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int result;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        dfs(sx, sy, 0, 0);
    }

    public static void dfs(int x, int y, int cnt, int key) {
        if (arr[x][y] == '1') {
            result = Math.min(result, cnt);
            return;
        }

        if (Character.isLowerCase(arr[x][y])) {
            if ((key & (1 << arr[x][y] - 'a')) == 0) {
                key |= 1 << arr[x][y] - 'a';
            }
        }

        visit[x][y][key] = cnt;

        for (int i = 0; i < dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (arr[nx][ny] == '#' || (visit[nx][ny][key] != null && visit[nx][ny][key] <= cnt + 1)) continue;

            if (Character.isUpperCase(arr[nx][ny])) {
                if ((key & (1 << arr[nx][ny] - 'a')) == 0) continue;
            }

            dfs(nx, ny, cnt + 1, key);
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        if (result == Integer.MAX_VALUE) bw.write(-1+"");
        else bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new char[N][M];
        visit = new Integer[N][M][1 << 'f' - 'a' + 1];
        result = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = line.charAt(j);

                if (arr[i][j] == '0') {
                    arr[i][j] = '.';
                    sx = i;
                    sy = j;
                }
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

비트 연산을 이용해야 할 문제는 이제 조금씩 보이는 것 같다!