5121번(지구 온난화)

첫 시도

• bfs 변형문제
• 주변의 섬의 개수가 2개 미만이라면 바다로 변경
• 출력시 바다만 있는 행,열은 생략이 되어야 하기 때문에 왼쪽 상단 꼭짓점의 좌표, 오른쪽 하단 꼭짓점의 좌표를 이중 for문으로 완전 탐색
• 입력, 섬 갯수 카운트, 섬을 바다로 변경, 꼭짓점 계산, 출력까지 5번의 이중 for문 사용 → 5RC의 시간복잡도

해결

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static String[][]input;
    static int[]dr= {0, -1, 0, 1};
    static int[]dc= {-1, 0, 1, 0};
    static intR,C;
    static String[][]map;
    static LinkedList<Node>list= new LinkedList<>();
    public static void main(String[] ars) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        R= Integer.parseInt(st.nextToken());
        C= Integer.parseInt(st.nextToken());
        map= new String[R][C];
        for(int i = 0; i<R; i++){
            String[] input = br.readLine().split("");
            for(int j = 0; j<C; j++){
                map[i][j] = input[j];
            }
        }
        for(int i =0 ;i<R; i++){
            for(int j = 0; j<C; j++){
                if(map[i][j].equals("X")){
                    bfs(i,j);
                }
            }
        }

        for(int i = 0; i<list.size(); i++){
            int a =list.get(i).r;
            int b =list.get(i).c;
            map[a][b] = ".";
        }
        int x = Integer.MAX_VALUE;
        int y = Integer.MAX_VALUE;
        int a = 0;
        int b = 0;
        for (int i = 0; i <R; i++) {
            for (int j = 0; j <C; j++) {
                if(map[i][j].equals("X")){
                    x = Math.min(x,i);
                    y = Math.min(y,j);
                    a = Math.max(a,i);
                    b = Math.max(b,j);
                }
            }
        }

        for(int i = x; i<=a; i++){
            for(int j = y; j<=b; j++){
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }
    static void bfs(int r, int c){
        int landNum = 0;
        for(int i = 0; i<4; i++) {
            int nr = r +dr[i];
            int nc = c +dc[i];

            if(nr < 0 || nr >=R|| nc < 0 || nc >=C) {
                continue;
            }
            if (map[nr][nc].equals("X")) landNum++;
        }
        if (landNum < 2) {
            list.add(new Node(r,c));
        }
    }

}
class Node{
    int r;
    int c;

    public Node(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

참고

• 직접구현