[TIL] 124 [C#] Graph 코테 배추문제

---

Graph

---

배추 문제

유기농 배추 문제

1번째 코드

답은 맞지만 좀 더 간단하게 해고싶은..

using System;
using System.Text;

class Program
{
    static void Main()
    {
        
        bool[,] visit;
        int[,] field;
        int[] nums;

        int input = Convert.ToInt32(Console.ReadLine());
        StringBuilder sb = new StringBuilder();

        for (int n = 0; n < input; n++)
        {
            nums = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);

            visit = new bool[nums[0], nums[1]];
            field = new int[nums[0], nums[1]];

            for (int i = 0; i < nums[2]; i++)
            {
                int[] xy = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);
                field[xy[0], xy[1]] = 1;
            }
            int count = 0;

            for (int i = 0; i < nums[0]; i++)
            {
                for (int j = 0; j < nums[1]; j++)
                {
                    if (field[i, j] == 1 && visit[i, j] == false)
                    {
                        dfs(i, j);
                        count++;
                    }
                }
            }
            sb.AppendLine(count.ToString());
        }
        Console.WriteLine(sb.ToString());
        Console.ReadLine();

        void dfs(int a, int b)
        {
            visit[a, b] = true;
            if (a - 1 >= 0 && visit[a - 1, b] == false)
            {
                if (field[a - 1, b] == 1)
                {
                    dfs(a - 1, b);
                }
            }
            if (a + 1 < nums[0] && visit[a + 1, b] == false)
            {
                if (field[a + 1, b] == 1)
                {
                    dfs(a + 1, b);
                }
            }
            if (b - 1 >= 0 && visit[a, b - 1] == false)
            {
                if (field[a, b - 1] == 1)
                {
                    dfs(a, b - 1);
                }
            }
            if (b + 1 < nums[1] && visit[a, b + 1] == false)
            {
                if (field[a, b + 1] == 1)
                {
                    dfs(a, b + 1);
                }
            }
        }
    }
}

2번째 코드

int[] dx,dy로 상하좌우 체크
width,height 변수

using System;
using System.Text;


class Program
{
    static void Main()
    {
        
        bool[,] visit;
        int[,] field;
        int[] nums;
        int width;
        int height;

        int[] dx = { -1, 1, 0, 0 }; 
        int[] dy = { 0, 0, -1, 1 };

        int input = Convert.ToInt32(Console.ReadLine());
        StringBuilder sb = new StringBuilder();

        for (int n = 0; n < input; n++)
        {
            nums = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);

            width = nums[0];
            height = nums[1];

            visit = new bool[width, height];
            field = new int[width, height];

            for (int i = 0; i < nums[2]; i++)
            {
                int[] xy = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);
                field[xy[0], xy[1]] = 1;
            }
            int count = 0;

            for (int i = 0; i < width; i++)
            {
                for (int j = 0; j < height; j++)
                {
                    if(field[i, j] == 1&& !visit[i, j])
                    {
                        dfs(i, j);
                        count++;
                    }
                }
            }
            sb.AppendLine(count.ToString());
        }
        Console.WriteLine(sb.ToString());
        Console.ReadLine();

        void dfs(int a,int b)
        {
            visit[a,b] = true;

            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i];
                int y = b + dy[i];

                if (x >= 0 && x < width && y >= 0 && y < height)
                {
                    if (!visit[x, y] && field[x,y]==1)
                    {
                        dfs(x, y);
                    }
                }
            }
        }
    }
}

• dx,dy로 상하좌우 체크

---

잡담, 일기?

Graph
코드 예제문제
인접행렬 - 적합한 상황 :노드 연결 여부 확인이 빈번히 필요한 경우
인접리스트 - 적합한 상황 : 희소 그래프 - 메모리와 탐색 효율이 뛰어납니다.

---