메리

문제 제대로 안 읽고 오름차순인거 캐치 못하고 계속 삽질..

나는 왜그럴까.. 

import java.io.File;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

public class Main {
    static boolean[][] isChecked; //체크여부
    static int[][] map;           //지도
    static int mapSize;           //지도의 크기
    static Deque<int[]> queue = new ArrayDeque<>();   //방문할 좌표
    static int[] xmove = new int[]{-1, 1, 0, 0};           //상하좌우
    static int[] ymove = new int[]{0, 0, -1, 1};           //상하좌우
    static int townCnt = 0;
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        mapSize = Integer.parseInt(sc.nextLine());
        map = new int[mapSize][mapSize];
        isChecked = new boolean[mapSize][mapSize];

        //map 저장
        for(int i=0; i<mapSize; i++){
            String row = sc.nextLine();
            for(int j=0; j<row.length(); j++){
                map[i][j] = row.charAt(j) - '0';
            }
        }

        for(int i=0; i<mapSize; i++){
            for(int j=0; j<mapSize; j++){
                if(!isChecked[i][j] && map[i][j] == 1){ //방문체크 안되어있는 1값인 경우 시작
                    townCnt += 1; //단지 카운트
                    bfs(i, j);
                }
            }
        }
        System.out.println(townCnt);
        Collections.sort(townSizes);
        for(Integer cnt : townSizes){
            System.out.println(cnt);
        }
    }
    static List<Integer> townSizes = new ArrayList<>();
    public static void bfs(int x, int y){
        int townSize = 1;
        queue.add(new int[]{x, y});
        isChecked[x][y] = true;
        while(!queue.isEmpty()){
            int[] position = queue.poll();
            for(int i=0; i<4; i++){
                int newx = position[0] + xmove[i];
                int newy = position[1] + ymove[i];
                if(newx >= 0 && newy >= 0 && newx < mapSize && newy < mapSize
                    && map[newx][newy] == 1
                    && !isChecked[newx][newy]
                ){
                    queue.add(new int[]{newx, newy});
                    isChecked[newx][newy] = true;
                    townSize += 1;
                }
            }
        }

        townSizes.add(townSize);    
        
    }
}

DFS 사용

import java.io.File;
import java.util.Scanner;

public class Problem2606 {
    static int[][] map; //연결망
    static boolean[] isChecked; //체크여부
    static int computerCnt; //컴퓨터 개수
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        computerCnt = Integer.parseInt(sc.nextLine());
        int lineCnt = Integer.parseInt(sc.nextLine());
        isChecked = new boolean[computerCnt+1];
        map = new int[computerCnt+1][computerCnt+1];

        //map에 연결여부 넣기
        for(int i=1; i<=lineCnt; i++){
            String[] line = sc.nextLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
            map[a][b] = map[b][a] = 1;
        }

        dfs(1);
        System.out.println(virusCnt);
    }

    static int virusCnt = 0;
    public static void dfs(int start){
        isChecked[start] = true;
        for(int i=1; i<=computerCnt; i++){
            if(map[start][i] == 1 && !isChecked[i]){ //방문한 적 없고 연결1이면
                virusCnt+=1;
                dfs(i);
            }
        }
    }
}

(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하기

필요한 변수

로직

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int n,m;
    public static int[][] map;
    public static int[] xmove = {-1,1,0,0}; //상 하 좌 우
    public static int[] ymove = {0,0,-1,1};
    public static Deque<int[]> queue = new ArrayDeque<>();
    public static boolean[][] isChecked;
    public static int[][] cnt;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        n = Integer.parseInt(nm[0]); //행 개수
        m = Integer.parseInt(nm[1]); //열 개수
        map= new int[n][m]; //지도
        isChecked = new boolean[n][m]; //방문 여부
        cnt = new int[n][m];

        //지도 저장
        for(int i=0; i<n; i++){
            String row = br.readLine();
            for(int j=0; j<m; j++){
                map[i][j] = row.charAt(j) - '0';
            }
        }
        bfs();
        System.out.println(cnt[n-1][m-1]);

    }

    public static void bfs(){
        cnt[0][0] = 1;
        queue.offer(new int[]{0,0});

        while(!queue.isEmpty()){
            int[] position = queue.poll();
            int x = position[0];
            int y = position[1];

            //2. 상화좌우의 이동 가능 좌표 탐색
            for(int i=0; i<4 ;i++){
                int newx = x + xmove[i];
                int newy = y + ymove[i];

                //값이 1이어야 하며, check 안된 곳, 범위를 벗어나지 않아야 함.
                if(newx >= 0 && newy >= 0 && newx < n && newy < m
                && map[newx][newy] == 1
                && !isChecked[newx][newy]){
                    queue.offer(new int[]{newx,newy}); //3. 큐에 넣기
                    isChecked[newx][newy] = true; //방문여부 체크
                    cnt[newx][newy] = cnt[x][y] + 1; //다음 위치 cnt 기록
                }
            }

        }
    }

}