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

문제

리뷰

bfs로 풀면 되겠다는 생각은 하였다.
근데 정작 bfs를 완전히 숙지하지 못해 구현을 할 수가 없었다.
전체적인 흐름은 다음과 같다.
1. String 배열 maps를 2차원 char형의 배열로 변환한다
2. 각 요소를 돌며 각 요소를 방문하지 않았고, 요소값이 "X"가 아니면 bfs(x,y)를 호출한다.
	- 그 후 리턴 값을 리스트에 저장한다.
2-1. 현재 위치를 큐에 삽입하고 방문했다는 것을 boolean형 2차원 배열의 현재 위치에 저장한다.
2-2. 큐에서 하나의 요소를 꺼내
2-3. 현재 요소의 값을 하나의 변수에 누적한 후,
2-4. 현재 위치에서 상하좌우의 요소값들을 살펴
	- 배열의 크기를 벗어나지 않고
    - 요소 값이 X가 아니고
    - 방문한적 없는 위치라면
    - 큐에 해당 위치를 삽입한다.
    - 2-2 ~ 2-4과정을 큐가 비워질 때까지 반복한다.
2-5. 요소의 값들을 누적한 변수를 리턴한다.
3. 리스트를 오름차순 정렬을 하고
4. 리스트의 크기가 0이라면 리스트에 -1을 삽입하고
5. 리스트를 배열 형태로 변환하여 리턴한다.

덕분에 다른 코드를 보지 않고 혼자 로직을 짤 수 있게 되었다.

코드

import java.util.*;

class Solution {
    
    static boolean[][] visited;
    static char[][] map;
    
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    public Integer[] solution(String[] maps) {
        int[] answer = {};
        
        map = new char[maps.length][maps[0].length()];
        visited = new boolean[maps.length][maps[0].length()];
        
        List<Integer> list = new ArrayList<>();
        
        for(int i = 0; i< maps.length; i++){
            for(int y = 0; y < maps[i].length(); y++){
                map[i][y] = maps[i].charAt(y);
            }
        }
        
        for(int i = 0; i < map.length; i++){
            for(int y = 0; y < map[0].length; y++){
                if(visited[i][y] == false && map[i][y] != 'X'){
                    list.add(bfs(new Pos(i, y)));
                }
            }
        }
        
        Collections.sort(list);
        
        if(list.size() == 0){
            list.add(-1);
        }
        
        return list.toArray(new Integer[0]);
    }
    
    public static int bfs(Pos start){
        Queue<Pos> q = new LinkedList<>();
        q.add(start);
        visited[start.x][start.y] = true;
        
        int sum = 0;
        while(q.isEmpty() == false){
            Pos cur = q.poll();
            
            // map의 각 요소는 char형태(아스키 코드) 이므로 - '0'을 해줘야 실제 숫자 값이 저장된다.
            sum += map[cur.x][cur.y]-'0';
            for(int i = 0; i < dx.length; i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                if(check(nx, ny) && map[nx][ny] != 'X'){
                    q.add(new Pos(nx, ny));
                    visited[nx][ny] = true;
                }
            }
        }
        return sum;
    }
    
    public static boolean check(int nx, int ny){
    	// 행과 열 값이 배열의 크기 내의 값이고, 방문을 하지 않은 위치면 true 아니면 false
        // 이미 방문을 한 위치를 다시 방문하게 될 경우 무한 루프를 돌 수 있기 때문
        if(nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length && visited[nx][ny] == false){
            return true;
        }else return false;
    }
}

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