Level 2: 무인도 여행, BFS를 사용한 2차원 좌표계에서 고립된 영역 탐색

참고 문서

• Programmers: 무인도 여행

이 문서의 내용

2차원 좌표계를 표현하는 이중 배열에서 각 원소는 이동할 수 없는 X와 식량의 양을 표현하는 N(1~9)로 나타납니다.

이때 좌표계에서 고립된 영역은 3개입니다.

각 고립된 영역에서 식량의 합은 왼쪽부터 1 5+9+1+1+5+2+3+1=27 1입니다.

고립된 영역을 탐색하려면 전체 원소를 순회하며 각 원소의 좌표를 기준으로 BFS를 실행합니다.

가장 왼쪽 상단의 원소(0, 0)는 이동할 수 없는 X이므로 BFS를 실행하지 않습니다.

그다음 원소(1, 0)는 자신을 포함해 총 8개의 원소를 탐색하는데 성공합니다.

그리고 원소(2, 0)는 원소(1, 0)에 의해서 탐색되었으므로 BFS를 실행하지 않습니다.

이 과정을 반복하며 BFS가 실행된 모든 결과를 컨테이너에 수집하면 문제에서 요구하는 결과를 도출 할 수 있습니다.

Step 1: 노드를 표현하는 클래스

길 찾기를 위한 경로는 2차원 좌표계-이중 배열로 제공됩니다. 이를 표현하고 저장하기 위한 Node 클래스를 생성합니다.

public class Node
{
	public int x, y;
	public int food;
	
	public Node(int x, int y, int food)
	{
		this.x = x;
		this.y = y;
		this.food = food;
	}
}

코드		비고
Line 3	int x, y	2차원 좌표계 위의 x, y 좌표입니다.
Line 4	int food	노드에서 얻을 수 있는 식량입니다.

Step 2: BFS 구현

특정 노드에서 시작해서 이동할 수 없는 X를 제외한 주변 모든 노드를 탐색하는 BFS를 구현합니다.

• 이동할 수 없는 X에서 시작하는 경우 BFS를 실행하지 않고 즉시 종료합니다.
• 만약 BFS를 실행하였다면 주변 모든 노드를 탐색하고 식량의 총량을 리턴합니다.

public int bfs(String[] maps, int bx ,int by, int h, int w, boolean[][] visited)
{
	int[] dx = { 0, 1, 0, -1 };
	int[] dy = { -1, 0, 1, 0 };
	char c = maps[by].toCharArray()[bx];
	
	Queue<Node> q = new LinkedList<>();
	q.offer(new Node(bx, by, c - 48));
	visited[by][bx] = true;
	if (c == 'X')
		return 0;

	int food = 0;
	while (!q.isEmpty())
	{
		Node n = q.poll();
		food += n.food;
	
		for (int i = 0; i < 4; ++i)
		{
			int nx = n.x + dx[i];
			int ny = n.y + dy[i];
			if (nx < 0 || ny < 0 || nx >= w || ny >= h)
				continue;
			if (visited[ny][nx])
				continue;
			char nc = maps[ny].toCharArray()[nx];
			if (nc == 'X')
				continue;
			q.offer(new Node(nx, ny, nc - 48));
			visited[ny][nx] = true;
		}
	}
	
	return food;
}

코드		비고
Line 10:11	if (c == 'X') return 0	이동할 수 없는 X에서 시작하는 경우 BFS를 실행하지 않습니다.
Line 30	q.offer(new Node(nx, ny, nc - 48))	아직 탐색하지 않은 인접한 식량 노드를 BFS로 탐색합니다.
Line 35	return food	BFS 탐색 결과로 얻은 고립된 노드 그룹의 총 식량입니다.

Step 3: 전체 노드를 순회하며 BFS 실행

앞서 작성한 BFS는 기준 노드에서 시작하여 연결된 노드를 모두 탐색하면 종료합니다.

따라서 다음으로 고립된 노드 그룹을 찾기 위해서는 전체 노드를 순회하며 기준 노드를 피봇해야합니다.

public int[] solution(String[] maps)
{
	int h = maps.length;
	int w = maps[0].length();
	boolean[][] visited = new boolean[h][w];
	
	List<Integer> answer = new ArrayList<>();
	for (int y = 0; y < h; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			if (visited[y][x])
				continue;
			int food = bfs(maps, x, y, h, w, visited);
			if (0 < food)
				answer.add(food);
		}
	}

	if (answer.isEmpty())
		answer.add(-1);

	return Arrays.stream(answer.toArray(new Integer[answer.size()])).mapToInt(Integer::intValue).sorted().toArray();
}

코드		비고
Line 8:18	if (visited[y][x]) continue	이미 방문한 노드는 기준 노드에서 제외합니다.
	int food = bfs(maps, x, y, h, w, visited)	현재 노드를 기준으로 BFS를 시작합니다.
Line 20:21	if (answer.isEmpty()) answer.add(-1)	문제의 요구 사항대로 고립된 영역이 하나도 없으면 -1을 리턴합니다.
Line 23	Arrays.strem(...)	문제의 요구 사항대로 고립된 영역의 각 식량 총합을 오름차순으로 정렬합니다.

Step 4: 전체 코드

각 단계별로 구성된 전체 코드는 다음을 참고합니다.

import java.util.*;

public class Solution
{
	public class Node
	{
		public int x, y;
		public int food;
		
		public Node(int x, int y, int food)
		{
			this.x = x;
			this.y = y;
			this.food = food;
		}
	}
	
	public int[] solution(String[] maps)
	{
		int h = maps.length;
		int w = maps[0].length();
		boolean[][] visited = new boolean[h][w];
		
		List<Integer> answer = new ArrayList<>();
		for (int y = 0; y < h; ++y)
		{
			for (int x = 0; x < w; ++x)
			{
				if (visited[y][x])
					continue;
				int food = bfs(maps, x, y, h, w, visited);
				if (0 < food)
					answer.add(food);
			}
		}
		
		if (answer.isEmpty())
			answer.add(-1);
		
		return Arrays.stream(answer.toArray(new Integer[answer.size()])).mapToInt(Integer::intValue).sorted().toArray();
	}
	
	public int bfs(String[] maps, int bx ,int by, int h, int w, boolean[][] visited)
	{
		int[] dx = { 0, 1, 0, -1 };
		int[] dy = { -1, 0, 1, 0 };
		char c = maps[by].toCharArray()[bx];
		
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(bx, by, c - 48));
		visited[by][bx] = true;
		if (c == 'X')
			return 0;
		
		int food = 0;
		while (!q.isEmpty())
		{
			Node n = q.poll();
			food += n.food;
			
			for (int i = 0; i < 4; ++i)
			{
				int nx = n.x + dx[i];
				int ny = n.y + dy[i];
				if (nx < 0 || ny < 0 || nx >= w || ny >= h)
					continue;
				if (visited[ny][nx])
					continue;
				char nc = maps[ny].toCharArray()[nx];
				if (nc == 'X')
					continue;
				q.offer(new Node(nx, ny, nc - 48));
				visited[ny][nx] = true;
			}
		}
		
		return food;
	}
}