[BOJ] 9328번 열쇠

복기

데이터를 때에 따라 확장하자.

코드

• C++ 17

#include <stdio.h> #include <string.h> #include <queue>   using namespace std;   struct Elem {     int H, W; };   int H, W, T;   // 빌딩 밖도 탐색의 범위에 포함시켜 // 프로그래밍의 편의성을 가져간다. // 다시 말해, 왼쪽 맵을 오른쪽처럼 생각한다. // **.*     ...... // *..* --> .**.*. // ****     .*..*. //          .****. //          ......   char Map[102][102]; bool Keys[26]; bool IsVisited[102][102]; int dh[] = { -1, 1, 0, 0 }; int dw[] = { 0, 0, -1, 1 };   int bfs() {     int ans = 0;          queue<Elem> q;       // 추후 열쇠를 얻으면 탐색할 문들의 위치다.     queue<Elem> doorQ[26];       q.push({ 0, 0 });     IsVisited[0][0] = true;     while (false == q.empty())     {         auto [h, w] = q.front();         q.pop();           for (int i = 0; i < 4; ++i)         {             int nh = h + dh[i];             int nw = w + dw[i];               if (nh < 0 || nh >= H + 2 || nw < 0 || nw >= W + 2)                 continue;             else if (IsVisited[nh][nw] || Map[nh][nw] == '*')                 continue;               IsVisited[nh][nw] = true;             if (Map[nh][nw] == '$')                 ++ans;             else if ('A' <= Map[nh][nw] && Map[nh][nw] <= 'Z')             {                 int k = Map[nh][nw] - 'A';                 if (Keys[k] == false)                 {                     doorQ[k].push({ nh, nw });                     continue;                 }             }             else if ('a' <= Map[nh][nw] && Map[nh][nw] <= 'z')             {                 int k = Map[nh][nw] - 'a';                 Keys[k] = true;                 while (false == doorQ[k].empty())                 {                     q.push(doorQ[k].front());                     doorQ[k].pop();                 }             }             q.push({ nh, nw });         }     }       return ans; }   int main() {     scanf("%d", &T);     while (T--)     {         scanf("%d %d", &H, &W);         for (int h = 1; h <= H; ++h)         {             for (int w = 1; w <= W; ++w)             {                 char ch;                 scanf(" %c", &ch);                 if (ch != '.')                     Map[h][w] = ch;             }         }                  char k[26];         scanf("%s", k);         const char* kp = k;         while (*kp)         {             if (*kp == '0')                 break;                          Keys[*kp - 'a'] = true;             ++kp;         }           printf("%d\n", bfs());           memset(Map, 0, sizeof(Map));         memset(Keys, false, sizeof(Keys));         memset(IsVisited, false, sizeof(IsVisited));       } }

• C# 6.0

using System; using System.Collections.Generic;   namespace Csharp {     class Program     {         class Elem         {             public int H, W;             public Elem(int h, int w)             {                 H = h;                 W = w;             }         }           static int H, W, T;         static char[,] Map = new char[102, 102];         static bool[,] IsVisited = new bool[102, 102];         static bool[] Keys = new bool[26];         static int[] dh = { -1, 1, 0, 0 };         static int[] dw = { 0, 0, -1, 1 };         static Queue<Elem> Q = new Queue<Elem>();         static Queue<Elem>[] DoorQ = new Queue<Elem>[26];           static void Main(string[] args)         {             for (int i = 0; i < 26; ++i)                 DoorQ[i] = new Queue<Elem>();               T = Convert.ToInt32(Console.ReadLine());             for (int t = 0; t < T; ++t)             {                 var inputs = Console.ReadLine().Split();                 H = Convert.ToInt32(inputs[0]);                 W = Convert.ToInt32(inputs[1]);                              for (int h = 1; h <= H; ++h)                 {                     var line = Console.ReadLine();                     for (int w = 1; w <= W; ++w)                     {                         if (line[w - 1] != '.')                             Map[h, w] = line[w - 1];                     }                 }                   string k = Console.ReadLine();                 for (int i = 0; i < k.Length; ++i)                 {                     if (k[i] == '0')                         break;                       int idx = k[i] - 'a';                     Keys[idx] = true;                 }                   Console.WriteLine(bfs());                   Array.Clear(Map, 0, Map.Length);                 Array.Clear(Keys, 0, Keys.Length);                 Array.Clear(IsVisited, 0, IsVisited.Length);                 for (int i = 0; i < 26; ++i)                     DoorQ[i].Clear();             }         }           static int bfs()         {             int result = 0;               Q.Enqueue( new Elem(0, 0) );             IsVisited[0, 0] = true;             while (Q.Count != 0)             {                 Elem elem = Q.Dequeue();                   for (int i = 0; i < 4; ++i)                 {                     int nh = elem.H + dh[i];                     int nw = elem.W + dw[i];                       if (nh < 0 || nh >= H + 2 || nw < 0 || nw >= W + 2)                         continue;                     else if (IsVisited[nh, nw] || Map[nh, nw] == '*')                         continue;                       IsVisited[nh, nw] = true;                       if (Map[nh, nw] == '$')                         ++result;                     else if ('A' <= Map[nh, nw] && Map[nh, nw] <= 'Z')                     {                         int k = Map[nh, nw] - 'A';                         if (Keys[k] == false)                         {                             DoorQ[k].Enqueue(new Elem(nh, nw));                             continue;                         }                     }                     else if ('a' <= Map[nh, nw] && Map[nh, nw] <= 'z')                     {                         int k = Map[nh, nw] - 'a';                         Keys[k] = true;                         while (DoorQ[k].Count != 0)                             Q.Enqueue(DoorQ[k].Dequeue());                     }                       Q.Enqueue(new Elem(nh, nw));                 }             }               return result;         }     } }

• Python 3

from sys import stdin from collections import deque input = stdin.readline           dh = [ -1, 1, 0, 0] dw = [ 0, 0, -1, 1]   def bfs(Map, H, W, Keys):     global dh, dw       result = 0     isVisited = [ bytearray(W + 2) for h in range(H + 2) ]     q = deque()     doorQ = [ deque() for i in range(26) ]           q.append((0, 0))     isVisited[0][0] = 1       while len(q) != 0:         h, w = q.popleft()           for i in range(4):             nh, nw = h + dh[i], w + dw[i]               if nh < 0 or nh >= H + 2 or nw < 0 or nw >= W + 2:                 continue             elif isVisited[nh][nw] or Map[nh][nw] == ord('*'):                 continue                          isVisited[nh][nw] = 1             if Map[nh][nw] == ord('$'):                 result += 1             elif ord('a') <= Map[nh][nw] <= ord('z'):                 k = Map[nh][nw] - ord('a')                 Keys[k] = 1                 while len(doorQ[k]) != 0:                     q.append(doorQ[k].popleft())             elif ord('A') <= Map[nh][nw] <= ord('Z'):                 k = Map[nh][nw] - ord('A')                 if Keys[k] == 0:                     doorQ[k].append((nh, nw))                     continue             q.append((nh, nw))       return result   T = int(input()) while T:     H, W = map(int, input().split())     Map = [ bytearray(W + 2) for h in range(H + 2) ]     for h in range(1, H + 1):         line = input().rstrip()         for w in range(1, W + 1):             if line[w - 1] != '.':                 Map[h][w] = ord(line[w - 1])          Keys = bytearray(26)     for k in input().rstrip():         if k == '0':             break           Keys[ord(k) - ord('a')] = 1       print(bfs(Map, H, W, Keys))       T -= 1