[프로그래머스] 무인도 여행

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

프로그래머스

---

	public class Programmers_무인도여행 {
	static final int[] nX = {-1, 0, 1, 0};
	static final int[] nY = {0, 1, 0 ,-1};
	public static void main(String[] args) {
	System.out.println(Arrays.toString(new Programmers_무인도여행().solution(new String[]{"X591X","X1X5X","X231X", "1XXX1"})));
	System.out.println(Arrays.toString(new Programmers_무인도여행().solution(new String[]{"XXX","XXX","XXX"})));
	}
	private int[] solution(String[] maps){
	for(int i=0; i<maps.length; i++){
	maps[i] = maps[i].replaceAll("X", "0");
	}
	ArrayList<Integer> al = new ArrayList<>();
	Queue<Node> q = new LinkedList<>();
	int[][] arr = new int[maps.length][maps[0].length()];
	int[][] visited = new int[maps.length][maps[0].length()];
	for(int i=0; i<arr.length; i++){
	char[] cArr = maps[i].toCharArray();
	for(int j=0; j<cArr.length; j++){
	arr[i][j] = Integer.parseInt(String.valueOf(cArr[j]));
	if(arr[i][j]==0){
	visited[i][j] = 1;
	}
	}
	}
	for(int i=0; i<arr.length; i++){
	for(int j=0; j<arr[0].length; j++){
	if(visited[i][j] == 0){
	visited[i][j] = 1;
	q.add(new Node(i, j));
	}
	int tempSum = 0;
	while(!q.isEmpty()){
	Node curNode = q.poll();
	tempSum += arr[curNode.x][curNode.y];
	for(int k=0; k<4; k++){
	int nextX = curNode.x + nX[k];
	int nextY = curNode.y + nY[k];
	if (nextX >= 0 && nextY >= 0 && nextX < arr.length && nextY < arr[0].length && visited[nextX][nextY] == 0) {
	visited[nextX][nextY] = 1;
	q.add(new Node(nextX, nextY));
	}
	}
	}
	if(tempSum != 0){
	al.add(tempSum);
	}
	}
	}
	if(al.size() == 0){
	al.add(-1);
	}
	Collections.sort(al);
	int[] answer = new int[al.size()];
	for(int i=0; i<answer.length; i++){
	answer[i] = al.get(i);
	}
	return answer;
	}
	class Node{
	int x;
	int y;
	public Node(int x, int y){
	this.x = x; // 높이
	this.y = y; // 너비
	}
	}
	}

view raw Programmers_무인도여행.java hosted with ❤ by GitHub

---

 

그냥 기본적인 DFS, BFS 문제

나는 BFS를 통해 진행함