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

참고 문서

• Programmers: 무인도 여행

이 문서의 내용

• Step 1: 노드를 표현하는 클래스
• Step 2: BFS 구현
• Step 3: 전체 노드를 순회하며 BFS 실행
• Step 4: 전체 코드

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 클래스를 생성합니다.

java

닫기

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를 실행하였다면 주변 모든 노드를 탐색하고 식량의 총량을 리턴합니다.

java

닫기

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는 기준 노드에서 시작하여 연결된 노드를 모두 탐색하면 종료합니다.

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

java

닫기

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: 전체 코드

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

java

닫기

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;
‌}
}