[C#] 빙하 크기 구하기

문제

0은 바다, 1은 얼음으로 구성된 2차원 맵이 존재한다.

이때, 얼음 덩어리(1로 연결된 묶음)을 구분하고, 가장 큰 얼음 덩어리의 크기를 구하라

• 예시 입력 : {1, 0, 1, 1, 0}, {1, 0, 1, 0, 0}, {0, 0, 1, 0, 1}, {0, 1, 0, 1, 1}
• 예시 출력 : 5

상하좌우로만 연결된 1끼리만 같은 덩어리로 간주. 대각선은 연결로 치지 않는다.

 

풀이

internal class Class2
{
	static int[,] map = {
		{ 1, 0, 1, 1, 0 },
		{ 1, 0, 1, 0, 1 },
		{ 0, 0, 1, 0, 1 },
		{ 0, 1, 1, 0, 1 }
	};

	static bool[,] isVisited = new bool[map.GetLength(0), map.GetLength(1)];

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

	static int DFS(int x, int y)
	{
		isVisited[x, y] = true;
		int size = 1;

		for(int i = 0; i<map.GetLength(0); i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= 0 && ny >= 0 && nx < map.GetLength(0) && ny < map.GetLength(1))
			{
				if (!isVisited[nx, ny] && map[nx, ny] == 1)
				{
					size += DFS(nx, ny);
				}
			}
		}
		return size;
	}

	static void Main()
	{
		List<int> iceSize = new();

		for (int i = 0; i<map.GetLength(0); i++)
		{
			for(int j = 0; j<map.GetLength(1); j++)
			{
				if (!isVisited[i, j] && map[i, j] == 1)
				{
					int size = DFS(i, j);
					iceSize.Add(size);
				}
			}
		}

		int highestSize = 1;

		foreach(int x in iceSize)
		{
			if(x > highestSize)
				highestSize = x;
		}

		Console.WriteLine(highestSize);
	}
}

 

설명

DFS(깊이 우선 탐색) 을 활용.

DFS란?

루트 노드부터 시작해서 마지막 노드까지, 현재 분기를 완벽하게 탐색한 후 다음 분기로 넘어가며 모든 배열을 탐색하는 방법.

비슷한 개념으로 BFS(너비 우선 탐색) 이 존재한다.

개념

1. 자기 자신을 호출하며 탐색하는 재귀 호출의 형태로 진행

2. 탐색 노드의 방향을 결정하는 방향 벡터 존재

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

 3. 어떤 노드를 방문했는지 여부를 확인하기 위한 bool 배열 존재 : 이 배열의 크기는 입력된 배열의 크기와 동일하게 측정. 무한 루프를 탈출하기 위한 수단으로 활용된다.

bool[,] isVisited = new bool[map.GetLenth(0), map.GetLength(1)];

 

시간 복잡도는 O(V + E) / V = 노드 수, E = 간선(노드 간 연결) 수 로 이루어진다.

모든 노드를 최대 1번 씩 방문하므로 O(V) 와 노드와 연결된 간선들을 하나씩 확인하므로 O(E) 가 합쳐진 시간 복잡도를 가진다.

 

로직을 얼핏 보기엔 DFS 메서드로 진입하기 위한 이중for문의 동작이나, 재귀 호출 등의 형태로 비효율적이지 않나? 생각할 수 있는데, bool 배열을 통해 방문 여부 확인 과정으로 모든 노드에 대해 중복 없이 처리가 이루어지기 때문에 매우 효율적인 알고리즘이다.

Main 에서는 DFS에 진입하기 위한 이중for문과, 그 안에서 DFS과정을 모두 거치고 나서 도출되는 얼음 덩어리의 크기를 size에 저장, 해당 크기를 List에 저장하여 추후 가장 큰 얼음 덩어리의 크기를 도출하기 위해 사용한다.

 

가장 중요한 로직은 DFS 메서드로, Main 에서 1 노드가 감지되는 순간 최초로 진입하여 인접한 노드에 1이 있을 경우에 재귀 호출을 통해 size를 추론한다.

bool 배열 isVisited를 매 DFS마다 true 로 바꾸며 중복 여부를 확인하고, 최초 진입 시에 현재 탐색하고 있는 얼음 덩어리의 크기를 int size = 1; 로 초기화한다.

 

전체 얼음 덩어리의 크기는 DFS의 재귀 호출로 탐색하며, 이후 모든 인접한 1 노드를 탐색을 마치고 나면 백트래킹 과정으로 size를 도출하며 DFS를 종료한다.

 

백트래킹

모든 경우를 탐색하되, 더 이상 의미 없는 경우(이번 문제에서는 인접한 1 노드를 모두 탐색하고 더이상 1 노드가 인접하지 않은 상태일 때를 말한다)가 발생했을 때, 그 이전 단계로 되돌아가서 다른 경로를 탐색하는 알고리즘.

 

이번 문제에서는

size += DFS(nx, ny);
...
return size;

이 코드를 통해 백트래킹 기법이 사용되었다 라고 판단할 수 있다.

 

예시 상황을 들어보면

DFS(0,2)
  → DFS(0,3)
    → DFS(1,2)
      → DFS(2,2)
        → 더 이상 없음 → return 1
      ← return 1 → size += 1
    ← return 2 → size += 2
  ← return 3 → size += 3
← return 4 → size = 4 최종값

다음과 같이 더 이상 인접한 1 노드가 없을 때까지 탐색한 후, 해당 size를 반환하는 과정을 반복하며 값을 모으고 최초의 DFS 까지 반환되면 최종값이 도출되는 형태로 진행된다.