[BOJ][C#] 13565 침투

📕 문제

📌 링크

📗 접근 방식

BFS 방식으로 접근하였다.

BFS 진입 조건
1. (0,y) 좌표 중 전류가 흐르는 (좌표값이 0) 경우

Queue 에 Enqueue하는 조건
1. 해당 좌표가 격자 크기를 벗어나지 않는 경우
2. 방문한 적이 없는 경우
3. 전류가 흐르는 (좌표값이 0) 경우

BFS 종료 조건
1. x값이 m-1 이고 전류가 흐르는 (좌표값이 0) 경우 return true
2. BFS를 모두 돌았지만 return되지 못한 경우 return false

📘 코드

namespace BOJ
{
    class No_13565
    {
        const int MAX = 1002;

        static int m, n;
        static int[,] board = new int[MAX, MAX];
        static bool[,] visited = new bool[MAX, MAX];
        static Queue<(int,int)> q = new Queue<(int,int)> ();
        static int[] dx = new int[] { 1, 0, -1, 0 };
        static int[] dy = new int[] { 0, 1, 0, -1 };

        static void Main()
        {
            int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            m = inputs[0];
            n = inputs[1];

            for(int i=0 ;i< m;i++)
            {
                string s = Console.ReadLine();
                for(int j=0 ;j< n;j++)
                {
                    board[i, j] = int.Parse(s[j].ToString());
                }
            }

            bool flag = false;
            for(int j = 0 ; j < n ; j++)
            {
                if(board[0, j] == 0 && BFS(0, j))
                {
                    flag = true;
                    break;
                }
            }

            Console.WriteLine(flag == true ? "YES" : "NO");
        }

        static bool BFS(int x, int y)
        {
            for (int i = 0 ; i < m ; i++)
                for(int j = 0 ; j < n ; j++)
                    visited[i, j] = false;

            q.Clear();

            q.Enqueue((x, y));
            visited[x, y] = true;

            while(q.Count > 0)
            {
                var cur = q.Dequeue();
                var curX = cur.Item1;
                var curY = cur.Item2;

                if(curX == m - 1 && board[curX, curY] == 0)
                {
                    return true;
                }

                for (int dir=0 ;dir<4 ;dir++)
                {
                    var nx = curX + dx[dir];
                    var ny = curY + dy[dir];

                    if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                    if(visited[nx, ny] || board[nx, ny] == 1) continue;

                    q.Enqueue((nx, ny));
                    visited[nx, ny] = true;
                }
            }

            return false;
        }
    }
}

📙 오답노트

나름 로직을 틀리지 않게 짰다고 생각을 하고 제출하였지만 틀렸다고 결과가 나와서 굉장히 당황스러웠다. 검토를 해보니 "NO"를 출력해야했지만 "No"를 출력하고 있는 사소한 실수를 했던 것이다... 다음부터는 좀 더 주도면밀하게 문제를 읽고 파악하여 실수를 줄이도록 노력해야겠다.

📒 알고리즘 분류

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