[JAVA] BOJ 백준 9328번 - 열쇠

목차

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

---

1. 문제

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

---

2. 내가 푼 방법

문제에 나와있는 기능들을 실수 없이 구현한다면 어렵지 않은 문제라고 생각한다.

 

일단 나는 빌딩 바깥에서 출입할 수 있는 출입 위치를 먼저 가져왔다.

그 후에 문서를 훔치는데 열쇠 개수가 더 이상 늘어나지 않을 때까지 문서를 훔치기 위한 출입을 반복한다.

public static void solution() {
    // 바깥에서 들어갈 수 있는 위치 가져오기
    List<Tuple> inOut = getInOutSite();

    // 문서 훔치기
    while (true) {
        int keyCnt = key.size();

        for (Tuple start : inOut) {
            steal(start.x, start.y);
        }

        // 키 개수 변화 없으면 빠져나옴
        if (keyCnt == key.size()) break;
    }
}

 

getInOutSite 함수가 빌딩 출입 위치들을 가져오는 기능을 한다.

이때 이전에 출입할 수 있는 위치에서 방문할 수 있는 위치라면 visit 배열을 통해 확인하는 코드를 작성해 주었다.

public static List<Tuple> getInOutSite() {
    List<Tuple> start = new ArrayList<>();
    boolean[][] visit = new boolean[N][M];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if ((i == 0 || j == 0 || i == N-1 || j == M-1) && arr[i][j] != '*' && !visit[i][j]) {
                moveInner(i, j, visit);
                start.add(new Tuple(i, j));
            }
        }
    }

    return start;
}

public static void moveInner(int i, int j, boolean[][] visit) {
    Queue<Tuple> queue = new LinkedList<>();
    queue.add(new Tuple(i, j));

    while (!queue.isEmpty()) {
        Tuple t = queue.poll();
        int x = t.x;
        int y = t.y;

        if (x < 0 || y < 0 || x >= N || y >= M) continue;

        if (arr[x][y] == '*') continue;
        else if (Character.isUpperCase(arr[x][y]) && !key.contains(arr[x][y])) continue;

        if (visit[x][y]) continue;
        else visit[x][y] = true;

        queue.add(new Tuple(x-1, y));
        queue.add(new Tuple(x+1, y));
        queue.add(new Tuple(x, y-1));
        queue.add(new Tuple(x, y+1));
    }
}

---

3. 자바 코드

https://github.com/geujeog/BOJ/blob/main/B9328.java

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

class Main {
    static int N;
    static int M;
    static char[][] arr;
    static List<Character> key;
    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            arr = new char[N][M];
            key = new ArrayList<>();
            result = 0;

            for (int i = 0; i < N; i++) {
                String line = br.readLine();

                for (int j = 0; j < M; j++) {
                    arr[i][j] = line.charAt(j);
                }
            }

            String keys = br.readLine();
            for (int i = 0; i < keys.length(); i++) {
                key.add(Character.toUpperCase(keys.charAt(i)));
            }

            solution();

            bw.write(result+"\n");
        }

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

public static void solution() {
    // 바깥에서 들어갈 수 있는 위치 가져오기
    List<Tuple> inOut = getInOutSite();

    // 문서 훔치기
    while (true) {
        int keyCnt = key.size();

        for (Tuple start : inOut) {
            steal(start.x, start.y);
        }

        // 키 개수 변화 없으면 빠져나옴
        if (keyCnt == key.size()) break;
    }
}

    public static void steal(int i, int j) {
        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(i, j));

        boolean[][] visit = new boolean[N][M];

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            int x = t.x;
            int y = t.y;

            if (x < 0 || y < 0 || x >= N || y >= M) continue;

            if (visit[x][y]) continue;
            else visit[x][y] = true;

            if (arr[x][y] == '*') continue;
            else if (arr[x][y] == '$') {
                result++;
                arr[x][y] = '.';
            }
            else if (Character.isLowerCase(arr[x][y])) {
                if (!key.contains(Character.toUpperCase(arr[x][y]))) key.add(Character.toUpperCase(arr[x][y]));
                arr[x][y] = '.';
            }
            else if (Character.isUpperCase(arr[x][y])) {
                if (!key.contains(arr[x][y])) continue;
                else {
                    arr[x][y] = '.';
                }
            }

            queue.add(new Tuple(x-1, y));
            queue.add(new Tuple(x+1, y));
            queue.add(new Tuple(x, y-1));
            queue.add(new Tuple(x, y+1));
        }
    }

    public static List<Tuple> getInOutSite() {
        List<Tuple> start = new ArrayList<>();
        boolean[][] visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if ((i == 0 || j == 0 || i == N-1 || j == M-1) && arr[i][j] != '*' && !visit[i][j]) {
                    moveInner(i, j, visit);
                    start.add(new Tuple(i, j));
                }
            }
        }

        return start;
    }

    public static void moveInner(int i, int j, boolean[][] visit) {
        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(i, j));

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            int x = t.x;
            int y = t.y;

            if (x < 0 || y < 0 || x >= N || y >= M) continue;

            if (arr[x][y] == '*') continue;
            else if (Character.isUpperCase(arr[x][y]) && !key.contains(arr[x][y])) continue;

            if (visit[x][y]) continue;
            else visit[x][y] = true;

            queue.add(new Tuple(x-1, y));
            queue.add(new Tuple(x+1, y));
            queue.add(new Tuple(x, y-1));
            queue.add(new Tuple(x, y+1));
        }
    }

    public static class Tuple {
        int x;
        int y;

        public Tuple(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

---

4. 결과 및 회고

인덱스나 예외사항 확인을 실수하지 않고 한 번에 코드를 작성해서 뿌듯했다.

함수를 분리할수록 가독성도 좋아지고, 기능 하나하나를 작성하는데 집중하다 보니 실수도 줄어드는 것 같다.