백준 C# - 4963 +) 풀이

우리가 앞서 풀었던 문제는 상하좌우만 움직이는 문제이다. 하지만 이번 문제는 대각선까지 움직이는 것이 추가되었다. 이부분만 다르지 나머지 부분은 똑같다.

 

나머지 부분에 대한 설명은 아래 문제 참조

백준 C# - 2667 +) 풀이

---

대각선 + 상하좌우 움직이는 방법

대각선과 상하좌우로 움직이는 경우의수를 구하면 아래와 같이 9가지가 나온다.

01 상하좌우 코드

상하좌우를 확인하면서 구하는 코드는 아래와 같이 구했었다.

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

---

02 상화좌우 + 대각선 코드

위의 9가지 경우의 수를 코드로 구현해보면 아래와 같이 나온다. 손으로 직접 한 번 써보면 쉽게 이해할 수 있다.

static int[] dir = { -1, 0, 1};
for(int i = 0; i<3; i++)
{
    for(int j = 0; j<3;j++)
    {
        int newX = x + dir[i];
        int newY = y + dir[j];
     }
}

나머지 알고리즘은 2667와 동일해서 생략하겠다.

---

코드 전문

using System;
using System.Collections.Generic;
using System.Linq;
namespace baek2
{
    class Program
    {
        static int[,] graph;
        static int[] dir = { -1, 0, 1};

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

            for(int i = 0; i<3; i++)
            {
                for(int j = 0; j<3;j++)
                {
                    int newX = x + dir[i];
                    int newY = y + dir[j];
                    if (graph[newX, newY] == 1)
                    {
                        DFS(newX, newY);
                    }
                }
            }
            
        }
        public static void Main()
        {
            while (true)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int w = input[0];
                int h = input[1];
                if (w == 0 && h == 0) return;
                graph = new int[100, 100];
                for (int i = 1; i <= h; i++)
                {
                    string[] s = Console.ReadLine().Split();
                    for (int j = 1; j <= w; j++)
                    {
                        graph[j, i] = int.Parse(s[j - 1]);
                    }  
                }
                int count = 0;
                for (int i = 1; i <= h; i++)
                {
                    for (int j = 1; j <= w; j++)
                    {
                        if (graph[j, i] == 1)
                        {
                            count++;
                            DFS(j, i);

                        }
                    }
                }
                Console.WriteLine(count);
            }
        }
    }
}