[BOJ][C#] 21736 헌내기는 친구가 필요해

📕 문제

📌 링크

📗 접근 방식

탐색:

• 초기에 'I' 위치에서 시작하여 상하좌우로 이동하면서 'P'를 찾는다.
• BFS를 사용하여 탐색하며 이미 방문한 곳은 재방문하지 않도록 visited 배열을 사용한다.

BFS:

• 다음과 같은 조건들은 건너뛴다.
  • 범위 밖으로 나간다.
  • 벽('X')이다.
  • 이미 방문한 곳이다.
• 'P'를 찾을 때마다 count를 증가시킨다.

결과 출력:

• 'I'에서 시작하여 찾은 'P'의 개수를 출력한다. 만약 'P'를 찾지 못한 경우 "TT"를 출력한다.

📘 코드

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

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

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

                    if (board[i, j] != 'I') continue;
                    
                    q.Enqueue((i, j));
                    visited[i, j] = true;
                }
            }

            int count = 0;
            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 >= n || ny >= m) continue;
                    if (board[nx, ny] == 'X') continue;
                    if (visited[nx, ny] == true) continue;
                    
                    if (board[nx, ny] == 'P') count++;

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

            Console.WriteLine($"{(count == 0 ? "TT" : count)}");
        }
    }
}

📙 오답노트

📒 알고리즘 분류

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