[백준] 1012번 유기농 배추(C#)

문제

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

1012번: 유기농 배추

코드

using System;
using System.Collections.Generic;

class Dongsik
{
    static int[,] map;
    static bool[,] visited;
    static int x, y;
    static int[] dx = {0, 0, -1, 1}; // 좌우
    static int[] dy = {1, -1, 0, 0}; // 상하

    static void Main(string[] args)
    {
        int testCase = int.Parse(Console.ReadLine()); // test case : 2번

        for(int i = 0; i < testCase; i++)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            x = input[0]; // 가로 : 10
            y = input[1]; // 세로 : 8
            int totalCnt = input[2]; // 배추가 심어진 곳의 위치 : 17

            map = new int[x, y]; // init
            visited = new bool[x, y]; // init

            // 좌표 생성
            for(int j = 0; j < totalCnt; j++)
            {
                int[] inputXY = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                int xx = inputXY[0];
                int yy = inputXY[1];

                map[xx, yy] = 1; // 배추 심기
            }

            int cnt = 0;
            for(int a = 0; a < x; a++)
            {
                for(int b = 0; b < y; b++)
                {
                    if(map[a, b] == 1 && visited[a, b] == false) // 배추가 있고 미방문 상태라면?
                    {
                        BFS(a, b);
                        cnt++;
                    }
                }
            }
            Console.WriteLine(cnt);
        }
    }

    static void BFS(int a, int b)
    {
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((a, b));
        visited[a, b] = true;

        while(queue.Count > 0)
        {
            (int aa, int bb) = queue.Dequeue();
            for(int i = 0; i < 4; i++)
            {
                // 새로운 좌표 만들어주기
                int newA = aa + dx[i];
                int newB = bb + dy[i];

                if(newA >= 0 && newA < x && newB >= 0 && newB < y && map[newA, newB] == 1 && visited[newA, newB] == false)
                {
                    visited[newA, newB] = true;
                    queue.Enqueue((newA, newB));
                }
            }
        }
    }
}

고민

1. 우선 문제를 정리했다.

 

2. 그리고 아이디어를 적었다.

 

확실히 BFS문제를 3일동안 푸니까 문제를 어떻게 풀어야하고 어떤 재료가 필요한지 보인다.

MAP을 만들어야 한다면? MAP, VISITED, DX, DY를 만들어주고 BFS()인자로는 X, Y를 주면 된다.

BFS()에서는 WHILD문을 돌려가며 X, Y를 DX, DY만큼 이동시켜 판별해준다.

 

GRAPH가 나온다면? Array안에 list를 담아서 양방향 매핑(?)을 해주고

BFS()인자로는 START지점을 주면 된다.

 

모두가 위같은 로직으로 움직이진 않지만 전반적으로 BFS문제를 풀었을 때 위같은 순서(?)로 코드를 작성하면 문제가 풀렸다. 실버 1까지만 풀어봐서.. 그럴 수 있지만... 응... 아무튼 그렇다. 앞으로 더 높은 문제를 풀게 되었을 때 새로운 문제가 등장한다면 그때 다시 로직을 고민해봐야겠다.