[코딩테스트] BOJ 2178 미로 탐색 (실패)

자료구조, 코딩테스트/너비 우선 탐색(BFS)

[코딩테스트] BOJ 2178 미로 탐색 (실패)

RꞮbble 2026. 4. 19. 14:57

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

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력1

예체 출력1

예제 입력2

예제 출력2

예제 입력3

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력3

예제 입력4

예제 출력4

풀이

BFS 코드를 그대로 가져와서 풀어봤다.

코드1 - 오답

namespace BFS
{
    internal class BOJ2178_미로_탐색
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

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

        static void Main(string[] args)
        {
            string[] input1 = sr.ReadLine().Split(" ");
            string input2;

            int N = int.Parse(input1[0]);
            int M = int.Parse(input1[1]);

            int[,] board = new int[N, M];
            bool[,] visit = new bool[N, M];
            Queue<(int x, int Y)> queue = new Queue<(int X, int Y)>();

            int count = 0;
            int falseCount = 0;
            int trueCount = 0;

            // 미로 배열 초기화 
            for (int i = 0; i < N; i++)
            {
                input2 = sr.ReadLine();

                for (int j = 0; j < M; j++)
                {
                    board[i, j] = int.Parse(input2[j] + "");
                }
            }

            visit[0, 0] = true; // 방문 표시 남기기
            queue.Enqueue((0, 0)); // 해당 칸을 큐에 넣기 
            count++; // 방문한 칸수 늘리기.

            while (queue.Count > 0)
            {
                // front 빼기 
                (int X, int Y) cur = queue.Dequeue();

                if (cur.X == N - 1 && cur.Y == M - 1)
                {
                    break;
                }

                // 상하좌우 확인 후, 큐에 넣기 (파란색 칸이면서 아직 방문하지 않았다면)
                for (int dir = 0; dir < 4; dir++)
                {
                    // 상하좌우 좌표 구하기. 
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];

                    // 인덱스 범위에서 벗어나거나, 이미 방문한 칸이거나, 빨강칸이면
                    // 다음 좌표 검사하기.
                    if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                    {
                        continue;
                    }
                    if (visit[nx, ny] || board[nx, ny] != 1) // 방문을 했거나, 탐색할 수 없는 곳이면 
                    {
                        continue;
                    }

                    trueCount++;
                    visit[nx, ny] = true; // 방문했음을 표시
                    queue.Enqueue((nx, ny));
                    count++; // 방문한 칸수 늘리기.
                }

                if(trueCount < 1)
                {
                    count--;
                    trueCount = 0;
                }
            }

            sw.WriteLine(count);

            sw.Close();
            sr.Close();
        }
    }
}

원인

어떤 경로든 count 변수로 칸 수를 계산하고 있다.

trueCount < 1인 경우 count를 -1해주고 있지만, 이건 막다른 길에 도달했을 때만이다.

막다른 길 이전에 계산된 count 값은 감산해주고 있지 않고 있다. 그래서 오답이다.

코드2

namespace BFS
{
    internal class BOJ2178_미로_탐색
    {
        static string[] board;
        static int[,] dist;

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

        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        static void Main(string[] args)
        {
            string[] input1 = sr.ReadLine().Split(" ");

            int n = int.Parse(input1[0]);
            int m = int.Parse(input1[1]);

            board = new string[n];
            dist = new int[n, m];

            for(int i = 0; i < n; i++)
            {
                board[i] = sr.ReadLine();
                for (int j = 0; j < m; j++)
                {
                    dist[i, j] = -1;
                }
            }

            Queue<(int X, int Y)> queue = new Queue<(int X, int Y)>();

            queue.Enqueue((0, 0));
            dist[0, 0] = 0;

            while(queue.Count > 0)
            {
                (int X, int Y) cur = queue.Peek();
                queue.Dequeue();

                for (int dir = 0; dir < 4; dir++)
                {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];

                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 인덱스 범위를 넘어가면 continue
                    if (dist[nx, ny] >= 0 || board[nx][ny] != '1') continue; // dist에 채워진 값이거나(거리 체크가 된 것이거나) board에 표시된 것이 아니라면 continue

                    dist[nx, ny] = dist[cur.X, cur.Y] + 1; // 현재 위치값 + 1으로 거리값을 dist에 저장 
                    queue.Enqueue((nx, ny));
                }
            }

            sw.WriteLine(dist[n - 1, m - 1] + 1); // (0,0) 포함 

            sw.Close();
            sr.Close();
        }
    }
}

해결

visit bool 배열말고 dist라는 int 배열을 사용했다.

dist 배열은 (0,0)에서 해당 좌표까지의 거리를 저장하는 배열이다.

BFS를 돌면서 dist에 거리를 저장해두면 마지막에는 dist[N, M]에 거리가 저장이 된다.

그 거리가 바로 (0,0)에서 (N,M)까지의 최단 거리가 된다.

문제에서 " 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다."라고 했으므로 시작 지점 (0,0)을 포함시키면 dist[n-1, m-1] + 1이 정답이 된다.

복습1 풀이 (5/9)

(0,0)에서 (N-1, M-1)까지 가는데 걸리는 최소 칸 수(최소 거리)를 구해야 한다.

이전에 배웠던 BFS 코드에 거리 배열을 추가해서 문제를 풀면 될 것 같다.

복습1 코드 - 오답

using System.Text;

namespace BFS
{
    internal class BOJ2178_미로탐색_복습1
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static StringBuilder sb = new StringBuilder();

        static Queue<(int x, int y)> queue = new Queue<(int x, int y)>();

        static int[,] board;
        static bool[,] visit;
        static int[,] lenArr;

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

        static void Main(string[] args)
        {
            string[] input1 = sr.ReadLine().Split(" ");
            int N = int.Parse(input1[0]);
            int M = int.Parse(input1[1]);

            // board, visit, lenArr init
            board = new int[N, M];
            visit = new bool[N, M];
            lenArr = new int[N, M];

            string input2;
            for(int i = 0; i < N; i++)
            {
                input2 = sr.ReadLine();
                for(int j = 0; j < M; j++)
                {
                    board[i, j] = int.Parse(input2[j] + "");
                }
            }

            int len = 0;

            // BFS
            for(int i = 0; i < N; i++)
            {
                for(int j = 0; j < M; j++)
                {
                    // 방문할 수 있는 좌표이고, 방문한 적 없는 좌표이면 
                    if (board[i, j] == 1 && !visit[i, j])
                    {
                        visit[i, j] = true; // 방문 표시 
                        lenArr[i, j] = ++len; // 길이 배열에 길이 추가 
                        queue.Enqueue((i, j)); // 큐에 (i, j)를 넣어서 상하좌우로 탐색할 수 있게 하기. 
                    }
                    // 방문ㄴ할 수 없는 좌표이고, 방문한 적이 있는 좌표이면 
                    else
                        continue; // 넘어가기. 

                    // 상하좌우 탐색
                    while(queue.Count > 0)
                    {
                        // 기준 좌표 가져오기. 
                        (int x, int y) curPos = queue.Dequeue();

                        bool isFirst = true;
                        for(int dir = 0; dir < 4; dir++)
                        {

                            // 기준 좌표의 상하좌우 좌표 구하기.
                            int posX = curPos.x + dx[dir];
                            int posY = curPos.y + dy[dir];

                            // 기준 좌표의 상하좌우 좌표가 인덱스 범위를 벗어나면 
                            if (posX < 0 || posX >= N || posY < 0 || posY >= M) continue; // 넘어가기.

                            // 기준 좌표의 상하좌우 좌표가 방문할 수 없는 좌표이거나, 이미 방문한 좌표이면
                            if (board[posX, posY] == 0 || visit[posX, posY]) continue; // 넘어가기.

                            // 기준 좌표의 상하좌우 좌표가 인덱스 범위를 벗어나지 않았고
                            // 방문할 수 있는 좌표이거나, 방문한 적 없는 좌표이면 
                            visit[posX, posY] = true; // 방문 표시
                            if (isFirst)
                            {
                                isFirst = false;
                                len++;
                            }
                            lenArr[posX, posY] = len; // 길이 배열에 길이 추가 
                            queue.Enqueue((posX, posY)); // 큐에 (i, j)를 넣어서 상하좌우로 탐색할 수 있게 하기. 
                        }
                    }
                }
            }

            sb.Append($"{lenArr[N - 1, M - 1]}");

            sw.WriteLine(sb.ToString());

            sw.Close();
            sr.Close();
        }
    }
}

최소 칸(길이)을 계산하는 코드가 잘못된 것 같다.

lenArr[posX, posY]에는 기준 좌표까지의 칸 수에서 +1을 한 값을 넣어야 하는데 엉뚱한 값을 넣고 있었다.

복습1 코드2 - 정답

using System.Text;

namespace BFS
{
    internal class BOJ2178_미로탐색_복습1
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static StringBuilder sb = new StringBuilder();

        static Queue<(int x, int y)> queue = new Queue<(int x, int y)>();

        static int[,] board;
        static bool[,] visit;
        static int[,] lenArr;

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

        static void Main(string[] args)
        {
            string[] input1 = sr.ReadLine().Split(" ");
            int N = int.Parse(input1[0]);
            int M = int.Parse(input1[1]);

            // board, visit, lenArr init
            board = new int[N, M];
            visit = new bool[N, M];
            lenArr = new int[N, M];

            string input2;
            for(int i = 0; i < N; i++)
            {
                input2 = sr.ReadLine();
                for(int j = 0; j < M; j++)
                {
                    board[i, j] = int.Parse(input2[j] + "");
                }
            }

            int len = 0;

            // BFS
            for(int i = 0; i < N; i++)
            {
                for(int j = 0; j < M; j++)
                {
                    // 방문할 수 있는 좌표이고, 방문한 적 없는 좌표이면 
                    if (board[i, j] == 1 && !visit[i, j])
                    {
                        visit[i, j] = true; // 방문 표시 
                        lenArr[i, j] = ++len; // 길이 배열에 길이 추가 
                        queue.Enqueue((i, j)); // 큐에 (i, j)를 넣어서 상하좌우로 탐색할 수 있게 하기. 
                    }
                    // 방문ㄴ할 수 없는 좌표이고, 방문한 적이 있는 좌표이면 
                    else
                        continue; // 넘어가기. 

                    // 상하좌우 탐색
                    while(queue.Count > 0)
                    {
                        // 기준 좌표 가져오기. 
                        (int x, int y) curPos = queue.Dequeue();

                        bool isFirst = true;
                        for(int dir = 0; dir < 4; dir++)
                        {

                            // 기준 좌표의 상하좌우 좌표 구하기.
                            int posX = curPos.x + dx[dir];
                            int posY = curPos.y + dy[dir];

                            // 기준 좌표의 상하좌우 좌표가 인덱스 범위를 벗어나면 
                            if (posX < 0 || posX >= N || posY < 0 || posY >= M) continue; // 넘어가기.

                            // 기준 좌표의 상하좌우 좌표가 방문할 수 없는 좌표이거나, 이미 방문한 좌표이면
                            if (board[posX, posY] == 0 || visit[posX, posY]) continue; // 넘어가기.

                            // 기준 좌표의 상하좌우 좌표가 인덱스 범위를 벗어나지 않았고
                            // 방문할 수 있는 좌표이거나, 방문한 적 없는 좌표이면 
                            visit[posX, posY] = true; // 방문 표시
                            lenArr[posX, posY] = lenArr[curPos.x, curPos.y] + 1; // 길이 배열에 길이 추가 
                            queue.Enqueue((posX, posY)); // 큐에 (i, j)를 넣어서 상하좌우로 탐색할 수 있게 하기. 
                        }
                    }
                }
            }

            sb.Append($"{lenArr[N - 1, M - 1]}");

            sw.WriteLine(sb.ToString());

            sw.Close();
            sr.Close();
        }
    }
}

lenArr[posX, posY]에 기준 좌표까지의 칸 수에서 +1을 한 값을 넣어주니 통과했다.

'자료구조, 코딩테스트 > 너비 우선 탐색(BFS)' 카테고리의 다른 글

[코딩테스트] Programmers - 네트워크 (실패) (0)	2026.05.28
[코딩테스트] BOJ 1926 그림 (성공) (0)	2026.04.18
[자료구조] BFS(너비 우선 탐색) (0)	2026.04.18

현재글[코딩테스트] BOJ 2178 미로 탐색 (실패)

회고록

ribblestudy 님의 블로그 입니다.

게임 클라이언트 개발자, 너비 우선 탐색, Unity, 힙, 자료구조, BFS, Til, 111퍼센트, heap, Boyer_Moore, Quick Sort, deque, 개인 프로젝트, Today I Learned, sqrMagnitude, Merge Sort, LLM, counting sort, 스택, C#, shader, 연결리스트, DFS, Rigidbody, GitHub Desktop, 코딩테스트, magnitude, 깊이 우선 탐색, Radix Sort, 유니티,

Today :
Yesterday :

회고록