14. 4963번 섬의 개수

 

4963번: 섬의 개수

 

2차원 배열을 써서 풀었음

배열에 값을 넣고 8방향으로 탐색하는 게 어려워서 검색해봤더니 그래프, DFS, BFS 문제라고 한다.

 

그래프는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 여려개의 고립된 부분 그래프로 구성될 수 있다.

트리와 다르게 루트, 노드의 개념이 없다.

일반적으로 DFS, BFS 로 탐색한다.

 

DFS(Depth First Search - 깊이 우선 방식)으로 Stack 구조나 재귀함수를 사용하여 구현

  -> 모든 노드 방문 (완벽 탐색)

 

BFS(Breadth First Search - 너비 우선 방식)으로 Queue 구조를 이용해서 구현

  -> 최단 경로, 임의의 경로를 찾을 때 사용

 

나는 재귀호출을 이용해서 구현했으니깐 DFS방식을 사용함????

어쨌거나 탐색은 제대로 했는데 답이 자꾸 큰 값이 나와서 이상했는데

결과값 도출하고 섬 갯수를 초기화를 안해서 누적된 거였음 

 

아무튼 맞긴 맞았는데 static이 너무 많다ㅋㅋ

나중에 정리해서 다시 풀어봐야겠다

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace _4963
{

    class Program
    {
        static int w;
        static int h;

        static int islandCount = 0;
        static int[] ax = { 0, 1, 1, 1, 0, -1, -1, -1 };
        static int[] ay = { 1, 1, 0, -1, -1, -1, 0, 1 };
        static int[,] map;
        static bool[,] visited;

        static void Main(string[] args)
        {
            while(true)
            {
                string[] input = Console.ReadLine().Split(' ');
                w = int.Parse(input[0]);
                h = int.Parse(input[1]);

                if (w == 0 && h == 0)
                {
                    break;
                }

                map = new int[h, w];
                visited = new bool[h, w];

                for (int i=0; i<h; i++)
                {
                    string[] landInput = Console.ReadLine().Split(' ');

                    for (int j=0; j<w; j++)
                    {
                        map[i, j] = int.Parse(landInput[j]);
                                               
                    }
                }

                for (int i = 0; i < h; i++)
                {
                    for (int j = 0; j < w; j++)
                    {    
                        if (!visited[i, j] && map[i, j] > 0)
                        {
                            ExamIsland(i, j);
                            islandCount++;
                        }

                    }
                }

                Console.WriteLine(islandCount);
                islandCount = 0;
                
            }

        }

        static void ExamIsland(int y, int x)
        {
            if(map[y,x]==0||visited[y,x])
            {
                return;
            }

            visited[y, x] = true;

            int dx = 0;
            int dy = 0;

            for(int i=0; i<8; i++)
            {
                dx = x + ax[i];
                dy = y + ay[i];

                if (dx>=0 && dx<w && dy>=0 && dy<h)
                {
                    ExamIsland(dy, dx);
                }
            }
        }
 
    }
}

 

그래프의 개념

[자료구조] 그래프(Graph)란 - Heee's Development Blog

DFS, BFS

[Algorithm] DFS와 BFS 기본과 예제 문제

참고한 코드

 

백준 4963번 섬의 개수