[ BOJ/C# ] 1012 유기농 배추

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

1012번: 유기농 배추

탐색 문제이다. 너비 우선 탐색인 bfs로 풀었다. 

이전에 푼 탐색 문제들은 탐색할 좌표가 딱 주어졌다면, 이 문제는 다음 탐색을 시작할 좌표도 찾아야 했다. 

using System;
using System.Text;
using System.IO;

namespace B1012
{
    class Program
    {
        static int M, N, K;
        static int[,] map = new int[51, 51];
        static bool[,] visted = new bool[51, 51];
        static Queue<(int, int)> q = new Queue<(int, int)>();
        static int warm;

        static int[] dx = { -1, 1, 0, 0 };
        static int[] dy = { 0, 0, -1, 1 };
        static void BFS(int x, int y) 
        {
            q.Enqueue((x,y));
            visted[x, y] = true;
            while (q.Count > 0)
            {
                (int,int) cur = q.Dequeue();
                int curx = cur.Item1;
                int cury = cur.Item2;
                //상하좌우
                for(int i = 0; i < 4; i++)
                {
                    curx = cur.Item1 + dx[i];
                    cury = cur.Item2 + dy[i];
                    //주어진 인덱스를 벗어나면 continue
                    if (curx < 0 || cury < 0 || curx > N || cury > M) continue;
                    //방문리스트에 이미 기록되었거나 배추가 없다면 continue
                    if (visted[curx, cury] == true || map[curx, cury] == 0) continue;
                    visted[curx, cury] = true;
                    q.Enqueue((curx, cury));
                }
            }
        }

        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();

            int t = int.Parse(sr.ReadLine());   //테스트 케이스
            for(int i = 0; i < t; i++)
            {
                //초기화
                Array.Clear(map);
                Array.Clear(visted);
                warm = 0;

                int[] mnk = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
                M = mnk[0];
                N = mnk[1];
                K = mnk[2];
                for (int j = 0; j < K; j++)
                {
                    int[] xy = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
                    map[xy[1]+1, xy[0]+1] = 1;
                }

                for(int j = 1; j <= N; j++)
                {
                    for (int k = 1; k <= M; k++)
                    {
                        if (map[j, k] == 1 && visted[j, k] == false)
                        {
                            BFS(j, k);
                            warm++;
                        }
                    }
                }
                sb.Append(warm + "\n");
            }
            sw.Write(sb);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}