백준 C# - 1012 +) 풀이

먼저 문제 이해부터 해보자

문제에서 배추 흰지렁이가 한 배추의 상하좌우로 다른 배추로 이동할 수 있다고 나와있다.

1) DFS를 이용해서 상하좌우로 이동할 수 있을때까지 이동하면서 확인해야 한다.

2) 그 그룹의 끝에 다다랐으면 다음으로 배추가 심어진 곳을 찾아 배추가 심어진 곳이 없을때까지 이를 반복하면 된다.

---

상하좌우 탐색에서 -값이 나오는 경우를 먼저 살펴보자

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

문제를 표로 나타내면 아래와 이미지와 같다.

---

 상하좌우 탐색

static int[] dirX = { 1, -1, 0, 0 };
static int[] dirY = { 0, 0, 1, -1 };

만약 x가 0이고 y가 4인 경우

for (int i = 0; i < 4; i++)
{
    int newX = x + dirX[i];
    int newY = y + dirY[i];
    if (graph[newX, newY] == 1)
}

반복문이 순서대로 실행되면 

-1인 경우가 생긴다 그러므로 -값이 생기지 않도록 그래프의 값을 +1씩한 위치에 추가해야 한다.

---

visited을 사용하는 경우

01 입력 받기

int k = int.Parse(Console.ReadLine());
while (k > 0)
{
    int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int M = input[0];
    int N = input[1];
    int K = input[2];
    graph = new int[2501, 2501 ]; // graph 초기화
    visited = new bool[2501, 2501]; // visited 초기화
    ...
}

---

02 graph 입력 받기

for (int i = 0; i < K; i++)
{
    int[] edge = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int u = edge[0];
    int v = edge[1];

    graph[u + 1, v + 1] = 1; // 위의 그림에서 설명과 같이 +1씩한 위치에 값을 넣기
}

---

03  DFS정의

반복문을 통해 상하좌우를 움직이면서 해당 위치에 배추가 심어져있고 아직 방문하지 않았다면 DFS함수를 재귀적으로 호출하여 해당 위치로 이동한다.

static void DFS(int x, int y)
{
    visited[x,y] = true; // 현재 위치 방문 표시

    for(int i = 0; i<4;i++)
    {     
        int newX = x + dirX[i];
        int newY = y + dirY[i];
        
        if (graph[newX,newY] == 1 && !visited[newX,newY])
            DFS(newX, newY);
    }
}

---

04 정답 출력

int answer = 0;
for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= M; j++)
    {
        if (graph[j, i] == 1)
        {
            DFS(j, i);
            answer++;
        }
    }
}
Console.WriteLine(answer);

 

i랑 j를 헷갈리지 말자

입력 값을 기준으로 (0,4)에서 0은 i이고 4는j에 해당된다. 그러므로 j가 가로의 값이고 i가 세로의 값이므로 DFS에는 X값에는 j, Y값에는 i를 넣어주어야 한다. 만약 헷갈린다면 직접 써보는 것을 추천한다.

---

visited을 사용하지 않는 경우

visited를 사용하지 않고 문제를 해결할 수 있다. 

visited 배열을 사용하지 않게되면서 메모리를 줄일 수 있으므로 visited배열이 필요한지 여부를 한번 생각해보고 필요하지 않는 경우 사용하지 않는 것이 좋다.

03 DFS정의

graph[x,y] = 0을 통해 방문을 표시를 하면서 해당 위치를 다시 방문하지 않게 한다.

static void DFS(int x, int y)
{
    graph[x, y] = 0;

    for (int i = 0; i < 4; i++)
    {
        int newX = x + dirX[i];
        int newY = y + dirY[i];
        if (graph[newX, newY] == 1)
            DFS(newX, newY);
    }
}

---

코드 전문

using System;
using System.Collections.Generic;

namespace baek2
{

    class Program
    {
        static int[,] graph;
        static int[] dirX = { 1, -1, 0, 0 };
        static int[] dirY = { 0, 0, 1, -1 };
        static void DFS(int x, int y)
        {
            graph[x, y] = 0;

            for (int i = 0; i < 4; i++)
            {
                int newX = x + dirX[i];
                int newY = y + dirY[i];
                if (graph[newX, newY] == 1)
                    DFS(newX, newY);
            }
        }
        public static void Main()
        {
            int k = int.Parse(Console.ReadLine());
            while (k > 0)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int M = input[0];
                int N = input[1];
                int K = input[2];
                graph = new int[2501, 2501];

                for (int i = 0; i < K; i++)
                {
                    int[] edge = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                    int u = edge[0];
                    int v = edge[1];

                    graph[u + 1, v + 1] = 1;

                }

                int answer = 0;
                for (int i = 1; i <= N; i++)
                {
                    for (int j = 1; j <= M; j++)
                    {
                        if (graph[j, i] == 1)
                        {
                            //Console.WriteLine($"{i} {j}");
                            DFS(j, i);
                            answer++;
                        }
                    }
                }
                Console.WriteLine(answer);
                k--;
            }

        }
    }
}