[programmers] 무인도 여행

문제
https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

 

---

< 무인도 여행 >

 

문제 풀이 (Java)

import java.util.*;

class Solution {
	public int[] solution(String[] maps) {

		int[][] arr = new int[maps.length][maps[0].length()];
		boolean visited[][] = new boolean[arr.length][arr[0].length];

		for (int i = 0; i < maps.length; i++) {
			for (int j = 0; j < maps[i].length(); j++) {
				if (maps[i].charAt(j) == 'X') {
					visited[i][j] = true;
				} else {
					arr[i][j] = maps[i].charAt(j) - '0';
				}
			}
		}

		ArrayList<Integer> list = new ArrayList<>();

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				if (!visited[i][j]) {
					visited[i][j] = true;
					list.add(bfs(arr, visited, i, j));
				}
			}
		}
		Collections.sort(list);

		int answer[] = { -1 };
		if (list.size() > 0) {
			answer = new int[list.size()];
			for (int i = 0; i < list.size(); i++) {
				answer[i] = list.get(i);
			}
		}
		return answer;
	}

	private static int bfs(int[][] arr, boolean visited[][], int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y });

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

		int result = arr[x][y];

		while (!queue.isEmpty()) {
			int position[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int x1 = position[0] + dx[i];
				int y1 = position[1] + dy[i];

				if (x1 >= 0 && x1 < visited.length && y1 >= 0 && y1 < visited[0].length && !visited[x1][y1]) {
					visited[x1][y1] = true;
					result += arr[x1][y1];
					queue.add(new int[] { x1, y1 });
				}
			}
		}
		return result;
	}
}

 

String maps[] 배열을 int[] arr 배열로 저장한다. 이때, 'X'라면 visited 배열에 true로 저장한다. visited 배열을 탐색하며 아직 방문하지 않은 곳이라면 방문 표시 및 bfs 함수를 호출한다. 반환값을 list에 저장한다. list를 오름차순으로 정렬 후 int[] answer 배열에 저장한다. 최종 answer을 반환한다. 

 

bfs 함수

: Queue에 시작 위치를 저장한다. Queue가 빌 때까지 다음 과정을 반복한다. Queue 값을 poll한 뒤 상하좌우를 살펴본다. 격자 범위 안이며 아직 방문하지 않은 곳이라면 방문 표시 및 머물 수 있는 값을 더하고, Queue에 저장한다. 머물 수 있는 값을 반환한다.  

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges