[BOJ][C#] 1743 음식물 피하기

LimJaeJun·2023년 8월 30일

algorithm boj

PS/BOJ

목록 보기

21/108

📕 문제

📌 링크

📗 접근 방식

BFS 방식으로 접근하였다.

BFS 진입 조건
1. (x,y)좌표에 방문한 적이 없고 음식물 쓰레기(값이 1)인 경우

Queue 에 Enqueue하는 조건
1. 해당 좌표가 격자 크기를 벗어나지 않는 경우
2. 방문한 적이 없는 경우
3. 음식물 쓰레기일 경우

BFS 종료 조건
BFS를 모두 완료할 때까지 진행시킨 후 count를 return한다.

return받은 count와 answer을 비교하며 최대값을 최신화시켜주면서 마지막에 answer을 출력해준다.

📘 코드

namespace BOJ
{
    class No_1743
    {
        const int MAX = 102;

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

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

            for(int count=0 ;count<k ;count++)
            {
                inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

                board[inputs[0] - 1, inputs[1] - 1] = 1;
            }
            
            for(int i=0 ;i<n ;i++)
            {
                for(int j=0 ;j<m ;j++)
                {
                    if(board[i, j] == 1 && !visited[i, j])
                        answer = Math.Max(answer, BFS(i, j));
                }
            }

            Console.WriteLine(answer);
        }

        static int BFS(int x, int y)
        {
            int count = 1;

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

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

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

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

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

            return count;
        }
    }
}