프로그래머스 | 무인도 여행 (Java)

🔒문제

프로그래머스 Lv2. 연습문제 무인도 여행

🔑해결

지도를 나타내는 문자열 배열 maps가 주어질 때, 연결되는 숫자들의 합을 배열에 담아 return하는 solution함수를 작성하는 문제이다.

여기서 지도를 나타내는 조건은

• 각 칸에는 'X' 또는 1에서 9 사이의 자연수
• 'X'는 바다를, 숫자는 무인도를 나타낸다
• 무인도는 상하좌우로 연결된다
  이다.

1. 방문 여부를 나타내기 위해 boolean[][] 배열 visited를 maps의 크기와 동일하게 생성
   1-1. visited와 map은 bfs 메서드에서도 사용하기 위해 전역변수로 생성하였다
2. 좌상에서 우하 방향으로 방문하지 않은 인덱스를 찾는다.
   2-1. 방문한 인덱스에 저장된 값이 'X'라면 방문 표시(visited[i][j] = true)만 한다
   2-2. 방문한 인덱스에 저장된 값이 숫자라면 bfs 메서드를 사용하여 해당 인덴스로부터 시작하는 연결된 숫자의 총합을 구한다.
3. LinkedList를 사용해 queue를 만들고 상하좌우 주변 노드를 방문하면서 숫자를 합한다.
   3-1. queue가 empty가 될 때까지 while문을 반복하며 연결된 노드를 탐색한다
   3-2. queue를 pop하여 해당 인덱스의 주변 노드를 for문을 통해 탐색한다.
   3-3. 방문한 인덱스의 저장된 값이 'X'라면 방문 표시만 한다.
   3-4. 숫자라면 sum에 합하고, 방문표시를 한다. 그리고 queue에 해당 인덱스를 add한다.
4. bfs메서드를 통해 구한 sum값을 list에 add한다.
   5-1. list에 저장된 데이터가 없다면 answer 배열에 -1를 담아 return한다.
   5-2. 데이터가 존재한다면 list를 배열로 변환하여 answer에 저장. 그리고 오름차순으로 정렬하여 return한다.

🔓코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

class Solution {
    
    String[] map;
	boolean[][] visited;
	
    public int[] solution(String[] maps) {
        int[] answer;
        
        visited = new boolean[maps.length][maps[0].length()];
        map = maps;
        
        ArrayList<Integer> list = new ArrayList<>();
        
        for (int i = 0; i < visited.length; i++) {
			for (int j = 0; j < visited[i].length; j++) {
				if (!visited[i][j]) {
					char target = maps[i].charAt(j);
					if (target == 'X') {
						visited[i][j] = true;
					} else {
						int sum = bfs(i, j);
						list.add(sum);
					}
				}
			}
		}
        
        if (list.size() == 0) {
        	answer = new int[1];
        	answer[0] = -1;
        } else {
        	answer = new int[list.size()];
        	for (int i = 0; i < answer.length; i++) {
        		answer[i] = list.get(i);
        	}
        	Arrays.sort(answer);        	
        }
        
        return answer;
    }
    
    private int bfs(int i, int j) {
    	int sum = 0;
    	
    	LinkedList<String> queue = new LinkedList<>();
    	int tn = map[i].charAt(j)-'0';
    	sum = tn;
    	queue.add(i + "," + j);
    	visited[i][j] = true;
    	
    	int[][] arnd = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 주변 노드	
    	
    	while(!queue.isEmpty()) { // queue가 empty가 될 때까지
    		String qp = queue.pop();
    		String[] qn = qp.split(",");
    		int x = Integer.parseInt(qn[0]);
    		int y = Integer.parseInt(qn[1]);
    		
    		for (int k = 0; k < arnd.length; k++) {
    			int tx = x + arnd[k][0];
    			int ty = y + arnd[k][1];
				if (tx >= 0 && tx < map.length 
                    && ty >= 0 && ty < map[0].length() 
						&& !visited[tx][ty]) { // 방문하지 않은 곳이라면
					tn = (map[tx].charAt(ty));

					if (tn != 'X') {
						sum += (tn - '0');
						queue.add(tx + "," + ty);
					}
					
					visited[tx][ty] = true;
				}
			}
    	}
    	
    	return sum;
    }
}