[BOJ]9328번 : 열쇠

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

9328번: 열쇠

 

 

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 비트 마스킹

 

문제 파악

1. 상근이가 빌딩에 침입해 문서를 훔치려 한다. 이때 빌딩은 '.' , '*', '$', 알파벳 대, 소문자로 이루어져 있다.
2. 대문자(문)에 해당되는 소문자(열쇠)를 상근이가 가지고 있을 경우 문을 따고 이동 가능하다.
3. 진입 가능한 모든 경로를 통해 훔칠 수 있는 문서의 최대 개수를 구한다.

 

이 문제를 처음 통과했을 때는 HashSet과 BFS 알고리즘을 활용하여 해결하였다.

그러나 메모리와 시간이 너무나 많이 소요되었고, 분명히 개선의 여지가 있기에 코드를 간결화하여 다시 풀기 시작하였다.

간결화한다고 수정했더니 오히려 시간 초과가 뜨는 경우도 발생하였고, 시간 초과를 벗어나니 문제가 틀리는 등 시행착오를 겪은 다음

아래와 같이 줄일 수 있었다.

 

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

public class Main {

    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };

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

        int TC = Integer.parseInt(br.readLine());

        while (TC-- > 0) {
            st = new StringTokenizer(br.readLine());
            
            boolean[] keys = new boolean[26];
            int H = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
            
            int answer = 0;
            char[][] building = new char[H+2][W+2];
            
            
            //가상의 벽면을 만들어서 진입 한다.
            for(int r=0;r<W+2;r++)
            {
                building[0][r] = building[H+1][r] = '.';
            }
            
            for(int r = 1; r<H+1; r++)
            {
                String str = br.readLine();
                building[r][0] = building[r][W+1] = '.';
                
                for(int c = 1; c<W+1;c++) {
                    building[r][c] = str.charAt(c-1);
                }
            }
            
            String key = br.readLine();

            if (!key.equals("0")) {
                for (int idx = 0; idx < key.length(); idx++) {
                   keys[key.charAt(idx) -'a'] = true;
                }
            }
            
            answer = Find(building,keys,0,0);

            bw.append(String.valueOf(answer));
            bw.newLine();
        }
        bw.flush();
        
    }

    private static int Find(char[][] building, boolean[] keys, int row, int col) {
        
        Queue<Point> q = new LinkedList<Point>();
        Queue<Point>[] lock = new Queue['Z'-'A'+1];        
        
        for(int idx = 0; idx<keys.length;idx++)
        {
            lock[idx] = new ArrayDeque<>();
        }

        int R = building.length;
        int C = building[0].length;
        int doc = 0;

        boolean[][] visited = new boolean[R][C];

        visited[row][col] = true;

        q.add(new Point(row, col));

        while (!q.isEmpty()) {
            int size = q.size();

            for (int sz = 0; sz < size; sz++) {
                Point p = q.poll();
                int x = p.x;
                int y = p.y;

                for (int cycle = 0; cycle < 4; cycle++) {
                    int cx = x + dx[cycle];
                    int cy = y + dy[cycle];
                    

                    if(cx <0 || cx>=R || cy<0 || cy>=C || visited[cx][cy]) continue;
                    
                    char c = building[cx][cy];
                    
                    if(c == '*') continue;
                    
                    visited[cx][cy] = true;
                    
                    if(c == '$') doc++;
                    else if(c>='A' && c<='Z')
                    {
                        if(!keys[c-'A']) {
                            lock[c-'A'].add(new Point(cx,cy));
                            continue;
                        }
                    }
                    else if(c>='a' && c<='z') {
                        keys[c-'a'] = true;
                        while (!lock[c - 'a'].isEmpty())
                            q.offer(lock[c - 'a'].poll());
                    }
                    
                    q.add(new Point(cx,cy));
                    
                }
            }
        }
        return doc;
    }
}

class Point {
    int x;
    int y;

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

개선의 아이디어는

1. Scanner 클래스 대신 BufferedReader, BufferedWriter를 사용

2. HashSet 대신 Character형 배열을 사용

3. 대문자 일 경우에 Queue <Point>[] lock = new Queue ['Z'-'A'+1]; 에 좌표를 넣어 두고 나중에 key를 찾을 경우 해당 좌표를 q에 넣고 탐색할 수 있도록 변경

 

3번 항목은 제출 후 맞은 사람에서 다른 분의 코드를 참조하여 활용하였다.