[BOJ][C#] 9238 열쇠

📕 문제

📌 링크

📗 접근 방식

• 보드를 입력 받을 때 외곽 테두리에 이동할 수 있는 빈 공간.을 추가하여
• BFS를 시작한다.
• 준비물
  • 열쇠를 가지고 있는지 판단할 수 있는 bool 배열
  • BFS를 탐색할 q
  • 상하좌우로 이동할 수 있는 dx, dy 배열
  • 방문 처리할 visited 배열
• 가지고 있는 키를 입력받아 key 배열에 저장한다.
• BFS 탐색시
• 예외처리
  • 범위 밖으로 나간 경우
  • 벽인 경우
  • 방문한 경우
• 해당 좌표가 다음과 같을 때
  • 열쇠인 경우
    • 열쇠를 저장
    • 큐에 담고 방문 처리
    • 해당 열쇠로 열 수 있는 문들을 큐에 담고 방문 처리
  • 문인 경우
    • 열쇠가 있는 경우
      • 큐에 담고 방문 처리
    • 열쇠가 없는 경우
      • 문전용 큐에 담음
  • 빈 공간인 경우
    • 큐에 담고 방문 처리
  • 문서인 경우
    • 정답을 증가
    • 큐에 담고 방문처리

📘 코드

using System.Text;

namespace BOJ_9328
{
    class Program
    {
        static void Main()
        {
            using StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
            
            StringBuilder sb = new StringBuilder();
            int t = int.Parse(sr.ReadLine());
            
            while (t-- > 0)
            {
                int[] inputs = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
                int h = inputs[0] + 2;
                int w = inputs[1] + 2;
                
                int answer = 0;

                bool[] keys = new bool[26];
                Queue<(int, int)>[] doors = new Queue<(int, int)>[26];
                for (int i = 0; i < 26; i++)
                {
                    doors[i] = new Queue<(int, int)>();
                }
                Queue<(int, int)> q = new Queue<(int, int)>();

                char[,] board = new char[h, w];
                bool[,] visited = new bool[h, w];
                
                int[] dx = { 1, 0, -1, 0 };
                int[] dy = { 0, 1, 0, -1 };
                
                // 외곽 테두리 추가
                for (int i = 0; i < h; i++)
                {
                    for (int j = 0; j < w; j++)
                    {
                        board[i, j] = '.';
                    }
                }
                
                for (int i = 1; i <= h-2; i++)
                {
                    string s = sr.ReadLine();
                    for (int j = 1; j <= w-2; j++)
                    {
                        board[i, j] = s[j-1];
                    }
                }

                string input = sr.ReadLine();
                if (input != "0")
                {
                    for (int i = 0; i < input.Length; i++)
                    {
                        keys[input[i] - 'a'] = true;
                    }
                }

                q.Enqueue((0, 0));
                visited[0, 0] = true;
                
                while (q.Count > 0)
                {
                    var cur = q.Dequeue();
                    int x = cur.Item1;
                    int y = cur.Item2;

                    for (int dir = 0; dir < 4; dir++)
                    {
                        int nx = x + dx[dir];
                        int ny = y + dy[dir];

                        // 보드 범위 밖으로 나간 경우
                        if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                        // 벽인 경우
                        if (board[nx, ny] == '*') continue;
                        // 방문한 경우
                        if (visited[nx, ny] == true) continue;
                        
                        // 열쇠인 경우
                        if (IsKey(board[nx, ny]))
                        {
                            // 열쇠 저장
                            keys[board[nx, ny] - 'a'] = true;
                            
                            // 열쇠면 해당 위치로는 갈 수 있으니 큐에 담아
                            q.Enqueue((nx, ny));
                            visited[nx, ny] = true;

                            // 해당 열쇠로 열 수 있는 문들을 큐에 담음
                            var tempQ = doors[board[nx, ny] - 'a'];
                            while (tempQ.Count > 0)
                            {
                                var temp = tempQ.Dequeue();
                                q.Enqueue(temp);
                                visited[temp.Item1, temp.Item2] = true;
                            }
                        }
                        
                        // 문인 경우
                        if (IsDoor(board[nx, ny]))
                        {
                            // 열쇠가 있는 경우
                            if (keys[board[nx, ny] - 'A'] == true)
                            {
                                // 큐에 담아
                                q.Enqueue((nx, ny));
                                visited[nx, ny] = true;
                            }
                            // 열쇠가 없는 경우
                            else
                            {
                                // 문 큐에 넣음
                                doors[board[nx, ny] - 'A'].Enqueue((nx, ny));
                            }
                        }
                        
                        // 빈 공간인 경우
                        if (board[nx, ny] == '.')
                        {
                            // 그냥 큐에 담음
                            q.Enqueue((nx, ny));
                            visited[nx, ny] = true;
                        }
                        
                        // 문서인 경우
                        if (board[nx, ny] == '$')
                        {
                            // 정답 증가시키고 큐에 담음
                            answer++;
                            q.Enqueue((nx, ny));
                            visited[nx, ny] = true;
                        }
                    }
                }

                sb.AppendLine($"{answer}");
            }
            
            
            
            sw.Write(sb);
            
            sr.Close(); sw.Flush(); sw.Close();
        }

        static bool IsKey(char alp) => alp is >= 'a' and <= 'z';
        static bool IsDoor(char alp) => alp is >= 'A' and <= 'Z';
    }
}

📙 오답노트

1. Dictionary를 이용하여 키와 문을 이용하였고 예제는 정답을 맞췄지만 반례를 찾지 못하여 처음부터 다시 로직을 작성하였다. 그리고 사실 굉장히 코드가 맘에 들지 않았던 이유도 큼.
   => 열쇠를 먹었다면 해당 문들을 모두 탐색하여 BFS로 상하좌우 체크하여 방문한 적이 있다면 큐에 담았는데 BFS안에 BFS라서 굉장히 복잡하고 더러운 코드였던 것 같다.

2. 테두리를 .로 추가하지 않고 테두리만 둘러보며 체크하였지만 answer이 증가하지 않았다.
   => 테두리만 .로 추가하여 제출하니 맞았다 => BFS 로직은 정답

📒 알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색