소프티어 장애물인식프로그램 java

문제링크

문제 접근

• bfs로 2차원 맵에서 이어지는 땅의 갯수 및 각 땅의 갯수 오름차순 출력

코드

import java.util.*;
import java.io.*;


public class Main
{
    static int N;
    static char[][] map;
    static boolean[][] visit;
    static int landCnt;
    static ArrayList<Integer> arr = new ArrayList<>();
    static int[] di = {1,-1,0,0};
    static int[] dj = {0,0,1,-1};
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visit = new boolean[N][N];
        for(int i=0;i<N;i++){
            String now = br.readLine();
            for(int j=0;j<N;j++){
                map[i][j] = now.charAt(j);
            }
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visit[i][j] && map[i][j] == '1') bfs(i,j);
            }
        }
        Collections.sort(arr);
        System.out.println(landCnt);
        for(int i=0;i<arr.size();i++){
            System.out.println(arr.get(i));
        }
    }
    private static void bfs(int starti, int startj){
        landCnt++;
        Queue<Integer> que = new LinkedList<>();
        que.add(starti);
        que.add(startj);
        visit[starti][startj] = true;
        int cnt = 1;
        while(!que.isEmpty()){
            int nowi = que.poll();
            int nowj = que.poll();
            for(int d=0;d<4;d++){
                int nexti = nowi + di[d];
                int nextj = nowj + dj[d];
                if(nexti<0 || nexti>=N || nextj<0 || nextj>=N || visit[nexti][nextj] || map[nexti][nextj]=='0') continue;
                que.add(nexti);
                que.add(nextj);
                visit[nexti][nextj] = true;
                cnt++;
            }
        }
        arr.add(cnt);
    }
}

결과

정리

• 소프티어 환경에서 연습
• BufferedReader, Collections 등등 자동완성 없으니 헷갈림