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

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

프로그래머스

 

문제 접근

편의상 1차원 배열인 maps를 2차원 char배열로 바꾸었다.

반복문을 돌면서 X도 아니고 방문하지 않은 지역을 발견하면 Pos타입의 큐에 값을 저장하고 bfs 탐색한 결과를 list에 추가한다.

bfs탐색에선 현재 탐색 위치를 방문 표시로 바꿔주고 상하좌우를 살피면서 똑같이 X도 아니고 방문하지 않은 지역을 발견하면 큐에 값을 저장하는 작업을 반복한다.

작업을 반복하면서 섬의 숫자를 합산, 큐에 값이 저장되지 않는다면 연결된 숫자가 없다는 뜻이기에 하나의 섬에 대한 탐색이 끝내고 반복문을 마저 돌면서 다음 탐색 지역이 있는지 확인한다.

 

반복문을 다 돌면 list 크기의 배열을 만들고 배열에 list의 값을 넣고 정렬 후 return 시켜준다.

import java.util.*;

class Pos{
	int x;
	int y;
	
	Pos(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

class Solution {
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static Queue<Pos> q = new LinkedList<>();
	static boolean[][] visit; 
	static int N;
	static int M;
	static char[][] map;
	
	public int[] solution(String[] maps) {
        
        N = maps.length;
        M = maps[0].length();
        
        visit = new boolean[N][M];
        map = new char[N][M];
        
        List<Integer> list = new ArrayList<Integer>();
        
        for(int i=0; i<N; i++) {
        	for(int j=0; j<M; j++) map[i][j] = maps[i].charAt(j);
        }
        
        for(int i=0; i<N; i++) {
        	for(int j=0; j<M; j++) {
        		if(map[i][j] != 'X' && visit[i][j] != true) {
        			q.add(new Pos(i, j));
        			list.add(bfs(i, j));
        		}
        	}
        }

        if(list.size() == 0) {
        	int[] answer = {-1};
        	return answer;
        }
        
        int[] answer = new int[list.size()];
        for(int i=0; i<answer.length; i++) answer[i] = list.get(i);
        
        Arrays.sort(answer);
        return answer;
    }
	
	public static int bfs(int x, int y) {
		
		visit[x][y] = true; // 탐색 시작 구간 방문 표시
		int count = 0;
		
		while(!q.isEmpty()) {
			
			Pos pos = q.poll();
			int posX = pos.x;
			int posY = pos.y;
			
			count += map[posX][posY] - 48;
			for(int i=0; i<4; i++) {
				int disX = posX + dx[i];
				int disY = posY + dy[i];
				
				if(disX >= N || disX < 0 || disY >= M || disY < 0) continue;
				
				if(map[disX][disY] != 'X' && visit[disX][disY] != true) {
					q.add(new Pos(disX, disY));
					visit[disX][disY] = true;
				}
			}
		}
		return count;
	}
}