코딩테스트/프로그래머스

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

jaewon_sss 2023. 1. 29. 15:08
반응형
import java.io.*;
import java.util.*;
class Solution {
    static int[][] deltas = {{0,1},{0,-1},{1,0},{-1,0}};
    static boolean[][] visited;
    static char[][] map;
    static int R,C;
    public int[] solution(String[] maps) {
        R = maps.length;
        C = maps[0].length();
        map = new char[R][C];
        visited = new boolean[R][C];
        for(int i=0; i< R; i++){
            map[i] = maps[i].toCharArray();    
        }
        for(char[] c: map){
            System.out.println(Arrays.toString(c));
        }
        List<Integer> list = new ArrayList<>();
        
        for(int r=0;r<R;r++){
            for(int c=0; c<C; c++){
                if(!visited[r][c] && map[r][c] != 'X'){
                    list.add(bfs(r,c));
                }
            }   
        }
        int[] answer;
        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);
            System.out.println(Arrays.toString(answer));
        }
        return answer;
    }
    public int bfs(int r, int c){
        int days = 0;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(r,c));
        visited[r][c] = true;
        while(!queue.isEmpty()){
            Point p = queue.poll();
            days += map[p.r][p.c]  - '0';
            for(int d=0; d<deltas.length; d++){
                int nr = p.r+deltas[d][0];
                int nc = p.c+deltas[d][1];
                if(isIn(nr,nc) && !visited[nr][nc] && map[nr][nc] != 'X'){
                    queue.offer(new Point(nr,nc));
                    visited[nr][nc] = true;
                }
            }
        }
        return days;
    }
    public boolean isIn(int r, int c){
        return 0<=r && r<R && 0<=c && c<C;
    }
    class Point{
        int r;
        int c;
        
        public Point(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}
반응형