[BOJ] 2206번 벽 부수고 이동하기

복기

전형적인 BFS 문제다. Python3에서 입력 받을 때, list comprehension을 쓰는 것보다 append() 하는 것이 좀 더 빠르게 나왔다.

코드

• C++ 17

#include <stdio.h> #include <queue>   using namespace std;   struct Elem {     int R, C, hadDestructed; };   int N, M; char Map[1001][1001]; int Dist[1000][1000][2];   int bfs() {     int dr[] = { -1, 1, 0, 0 };     int dc[] = { 0, 0, -1, 1 };     Dist[0][0][0] = 1;       queue<Elem> q;     q.push({ 0, 0, 0 });     while (false == q.empty())     {         auto [r, c, hadDestruted] = q.front();         q.pop();           if (r == (N - 1) && c == (M - 1))             return Dist[r][c][hadDestruted];           for (int i = 0; i < 4; ++i)         {             int nr = r + dr[i];             int nc = c + dc[i];               if (nr < 0 || nr >= N || nc < 0 || nc >= M)                 continue;             else if (Dist[nr][nc][hadDestruted])                 continue;               if (Map[nr][nc] == '0')             {                 Dist[nr][nc][hadDestruted] = Dist[r][c][hadDestruted] + 1;                 q.push({ nr, nc, hadDestruted });             }             else if (hadDestruted == false)             {                 Dist[nr][nc][1] = Dist[r][c][hadDestruted] + 1;                 q.push({ nr, nc, 1 });             }         }     }       return -1; }   int main() {     scanf("%d %d", &N, &M);     for (int r = 0; r < N; ++r)         scanf("%s", Map[r]);     printf("%d", bfs()); }

• C# 6.0

using System; using System.Collections.Generic;   namespace Csharp {     class Program     {         class Elem         {             public int R, C, HadDestructed;             public Elem(int r, int c, int h)             {                 R = r;                 C = c;                 HadDestructed = h;             }         }           static int N, M;         static string[] Map = new string[1000];         static int[,,] Dists = new int[1000, 1000, 2];           static void Main(string[] args)         {             var inputs = Console.ReadLine().Split();             N = Convert.ToInt32(inputs[0]);             M = Convert.ToInt32(inputs[1]);             for (int i = 0; i < N; ++i)                 Map[i] = Console.ReadLine();             Console.Write(bfs());         }           static int bfs()         {             Queue<Elem> q = new Queue<Elem>();             int[] dr = { -1, 1, 0, 0 };             int[] dc = { 0, 0, -1, 1 };             Dists[0, 0, 0] = 1;               q.Enqueue( new Elem(0, 0, 0) );             while (q.Count != 0)             {                 Elem elem = q.Dequeue();                   if (elem.R == (N - 1) && elem.C == (M - 1))                     return Dists[elem.R, elem.C, elem.HadDestructed];                   for (int i = 0; i < 4; ++i)                 {                     int nr = elem.R + dr[i];                     int nc = elem.C + dc[i];                       if (nr < 0 || nr >= N || nc < 0 || nc >= M)                         continue;                     else if (Dists[nr, nc, elem.HadDestructed] != 0)                         continue;                       if (Map[nr][nc] == '0')                     {                         Dists[nr, nc, elem.HadDestructed] = Dists[elem.R, elem.C, elem.HadDestructed] + 1;                         q.Enqueue(new Elem(nr, nc, elem.HadDestructed));                     }                     else if (elem.HadDestructed == 0)                     {                         Dists[nr, nc, 1] = Dists[elem.R, elem.C, elem.HadDestructed] + 1;                         q.Enqueue(new Elem(nr, nc, 1));                     }                 }             }               return -1;         }     } }

• Python 3

from sys import stdin from collections import deque input = stdin.readline   N, M = map(int, input().split()) Map = [] Q = deque() for i in range(N):     row = [ int(x) for x in input().rstrip() ]     Map.append(row)   def bfs(Map, N, M):     dr = [ -1, 1, 0, 0]     dc = [ 0, 0, -1, 1]     dist = []     dist = [[[0 for i in range(2)] for j in range(M) ] for k in range(N) ]     dist[0][0][0] = 1       Q.append((0, 0, 0))     while len(Q) != 0:         r, c, hadDestructed = Q.popleft()           if r == (N - 1) and c == (M - 1):             return dist[r][c][hadDestructed]           for i in range(4):             nr, nc = r + dr[i], c + dc[i]               if nr < 0 or nr >= N or nc < 0 or nc >= M:                 continue             elif dist[nr][nc][hadDestructed]:                 continue               if Map[nr][nc] == 0:                 dist[nr][nc][hadDestructed] = dist[r][c][hadDestructed] + 1                 Q.append((nr, nc, hadDestructed))             elif not hadDestructed:                 dist[nr][nc][1] = dist[r][c][hadDestructed] + 1                 Q.append((nr, nc, 1))       return -1   print(bfs(Map, N, M))