GOSE_KOSE

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번포스팅은 백준 SW 기출문제 연구소 3 자바 풀이를 진행하도록 하겠습니다.

문제출처: https://www.acmicpc.net/problem/17142

1. 풀이 소스

package sw_17142;

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        Virus virus = new Virus(n, m);
        
        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < n; col++)
                virus.setMap(row, col, parseInt(st.nextToken()));
        }
        
        virus.run();
        System.out.println(virus.getTime());
    }
}

class Virus {
    
    static final int[] DR = {-1, 0, 1, 0}; // 이동 row
    static final int[] DC = {0, -1, 0, 1}; // 이동 col
    
    int n; // n by n 행렬
    int m; // 선택해야 하는 조합 개수
    int time = Integer.MAX_VALUE; // 최소 시간을 위해 최대 시간 으로 초기화
    int brickCnt; // 벽 개수
    int[][] map; // 맵 설정
    int[][] visited; // 방문 여부 2차원 인트 배열
    int visitedCnt; // 방문 수
    int impossibleCnt; // 모두 불가능한 경우 판단
    List<Point> virus = new ArrayList<>(); // 바이러스 리스트
    boolean[] active; // 활성화 바이러스를 위한 백트래킹 불린 배열
    
    Virus (int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][n];
        visited = new int[n][n];
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
        if (value == 2) virus.add(new Point(row, col)); // 바이러스 포인트 리스트에 추가
        if (value == 1) brickCnt++; // 벽 개수 추가
    }
    
    void run() {
        active = new boolean[virus.size()]; // 활성화 벽 불린 배열 초기화
        combi(0, 0); // 재귀로 조합 설정하기
    }
    
    void combi(int idx, int k) {
        if (k == m) { // 확산 시키기
            visitedCnt++; // k == m 인 걍우의 조합
            int remainDiffusionCnt = n * n - brickCnt - virus.size(); // 남아있는 확산되어야 할 빈칸의 수
            Queue<Point> queue = new ArrayDeque<>(); // 큐에 넣기 위함 (bfs)
            for (int i = 0; i < active.length; i++) {
                if (active[i]) queue.add(virus.get(i)); // 활성바이러스 큐에 넣기
            } 
            
            int localTime = 0; // 지역 시간 설정
            while(!queue.isEmpty()) {
                Point p = queue.poll();

                if (visited[p.row][p.col] == visitedCnt) continue; // 방문한 경우 건너 뛰기
                visited[p.row][p.col] = visitedCnt; // 방문 설정
                if (map[p.row][p.col] == 0) remainDiffusionCnt--; // 빈 칸이라면 남아있는 확산 개수 줄이기

                if (remainDiffusionCnt == 0) {
                    localTime = p.time; // 선입 선출로 큐에 들어온 time은 증가 함수이므로 break;
                    break;
                }

                for (int i = 0; i < 4; i++) {
                    int nextR = p.row + DR[i];
                    int nextC = p.col + DC[i];
                    
                    if (!isValid(nextR, nextC)) continue;
                    queue.add(new Point(nextR, nextC, p.time + 1));
                }
            }
            
            if (remainDiffusionCnt != 0) impossibleCnt++; // 만약 남아있는 확산 cnt가 있다면 impossible 증가
            else time = Math.min(localTime, time); // 모두 확산 시킨경우 최소값으로 업데이트
                
            return;
        }

        // 재귀
        for (int i = idx; i < virus.size(); i++) {
            active[i] = true;
            combi(i + 1, k + 1);
            active[i] = false;
        }
    }

    int getTime() {
        if (visitedCnt == impossibleCnt) { // 만약 조합의 경우의 수가 모두 불가능한 경우
            time = -1;
        }

        return time;
    }
    
    boolean isValid(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < n && visited[row][col] != visitedCnt
            && map[row][col] != 1; 
    }
    
    static class Point {
        int row;
        int col;
        int time;
        
        Point (int row, int col, int time) {
            this.row = row;
            this.col = col;
            this.time = time;
        }
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

2. 풀이 중점 사항

재귀로 조합 설정하기

boolean 배열을 사용하여 k 개의 개수를 선택하는 조합형 문제를 재귀로 해결할 수 있습니다.

void combi(int idx, int k) {
	if (k == m) {
    	// 중략
    	return;
    }

    // 재귀
    for (int i = idx; i < virus.size(); i++) {
        active[i] = true;
        combi(i + 1, k + 1);
        active[i] = false;
    }
}

만약 combi 메서드를 호출하게 되면, k가 m이 될 때까지 반복문을 활용하면서 idx로 active를 활성화시키고 닫는 작업을 반복합니다. 이를 통해 총 q 개의 사이즈에서 m 개를 선택하는 조합을 완성시킬 수 있습니다.

방문 처리

visitedCnt++; // k == m 인 걍우의 조합
int remainDiffusionCnt = n * n - brickCnt - virus.size(); // 남아있는 확산되어야 할 빈칸의 수
Queue<Point> queue = new ArrayDeque<>(); // 큐에 넣기 위함 (bfs)
for (int i = 0; i < active.length; i++) {
    if (active[i]) queue.add(virus.get(i)); // 활성바이러스 큐에 넣기
} 

int localTime = 0; // 지역 시간 설정
while(!queue.isEmpty()) {
    Point p = queue.poll();

    if (visited[p.row][p.col] == visitedCnt) continue; // 방문한 경우 건너 뛰기
    visited[p.row][p.col] = visitedCnt; // 방문 설정
    if (map[p.row][p.col] == 0) remainDiffusionCnt--; // 빈 칸이라면 남아있는 확산 개수 줄이기

    if (remainDiffusionCnt == 0) {
        localTime = p.time; // 선입 선출로 큐에 들어온 time은 증가 함수이므로 break;
        break;
    }

    for (int i = 0; i < 4; i++) {
        int nextR = p.row + DR[i];
        int nextC = p.col + DC[i];

        if (!isValid(nextR, nextC)) continue;
        queue.add(new Point(nextR, nextC, p.time + 1));
    }

조합으로 최선의 시간을 구해야하는 문제의 경우 매번 boolean [][] 배열을 초기화하고 생성하는 것은 공간 복잡도를 증가시킵니다. 따라서, visitedCnt라는 인스턴스 변수를 선언하여 조합이 생성될 때마다 하나씩 증가시킵니다.

이 값은 하나의 조합에 대한 while루프가 종료될 때 까지 같은 값을 가지므로 특정 조합에 대한 유니크한 값을 가진다고 볼 수 있습니다. 따라서, 이러한 유니크한 값으로 업데이트되지 않은 visited [][]의 row, col은 방문하지 않았다고 판단하고 방문 설정 하는 것입니다. 이를 통해 매번 boolean[][] 으로 방문 처리를 하지 않더라도 유효한 방문 처리를 설정할 수 있습니다.

if (remainDiffusionCnt != 0) impossibleCnt++; // 만약 남아있는 확산 cnt가 있다면 impossible 증가
else time = Math.min(localTime, time); // 모두 확산 시킨경우 최소값으로 업데이트

remainDiffusionCnt는 남아있는 확산되어야 하는 빈칸의 개수로, 만약 빈칸이 확산되면 개수를 줄이고 0이라면 루프를 종료시키도록 하였습니다. 최종적으로 어떠한 조건의 만족으로 while 루프가 종료되었을 때, remainDiffusionCnt가 0이 아니라는 것은 모든 곳을 방문하지 못했지만 벽에 가로막혀 더 이상 확산 시키지 못했음을 의미합니다. 따라서, impossibleCnt 개수를 증가시킵니다.

그 외에 자세한 풀이는 주석화하였습니다. 이상으로 연구소 3 자바 풀이를 마치도록 하겠습니다. 감사합니다.!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 - 이차원 배열과 연산 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/17140

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = parseInt(st.nextToken());
        int c = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());
        
        ArrayCalculation array = new ArrayCalculation(r, c, k);
        
        for (int row = 1; row <= 3; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= 3; col++) {
                array.setMap(row, col, parseInt(st.nextToken()));
            }
        }
        
        array.start();
        System.out.println(array.getTime());
    }
}

class ArrayCalculation {
    int r; // 찾아야 하는 행
    int c; // 찾아야 하는 열
    int k; // 되어야 하는 값
    int time; // k가 되는데까지 걸린 시간
    int rowCnt = 3; // 처음 시작은 3 by 3 이므로 행의 개수
    int colCnt = 3; // 열의 개수
    int[][] map = new int[101][101]; // 총 열과 행의 개수는 100을 넘지 않음 (101 인 이유는 1행, 1열 부터 시작)
    Point[] points = new Point[101];
    
    ArrayCalculation (int r, int c, int k) {
        this.r = r;
        this.c = c;
        this.k = k;
        
        for (int i = 1; i <= 100; i++) points[i] = new Point(i); // 포인트 초기화
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }
    
    void start() {
        while(time < 101) {

            if (map[r][c] == k) return; // 종료 조건

            int nextRowCnt = rowCnt; // 다음 while문에 적용 할 RowCnt
            int nextColCnt = colCnt; // 다음 while문에 적용 할 ColCnt

            if (rowCnt >= colCnt) { // 행이 열보다 같거나 긴 경우
                for (int row = 1; row <= rowCnt; row++) {
                    List<Point> sortList = new ArrayList<>();
                    
                    for (int col = 1; col <= colCnt; col++) {
                        int value = map[row][col]; // map에 저장된 값

                        if (value == 0) continue;
                        Point p = points[value];

                        p.cnt++;
                        if (!p.in) { // 만약 p가 리스트에 없다면
                            p.in = true; // 리스트에 있다는 표시
                            sortList.add(p); // 리스트 추가
                        }
                    }

                    sortList.sort(Comparator.comparing((Point po) -> po.cnt)
                            .thenComparing(po -> po.num));

                    int idx = 1;
                    for (Point p : sortList) {
                        if (idx >= 101) break;
                        map[row][idx] = p.num; // 먼저 1번 인덱스 수
                        map[row][++idx] = p.cnt; // 그 다음 인덱스로 cnt
                        idx++; // idx 증가시키기
                    }
                    
                    for (int col = idx; col < 101; col++) {
                        map[row][col] = 0; // 남아있는 열은 모두 0으로 설정하기
                    }
                    
                    if (row == 1) nextColCnt = idx; // 변경된 col 개수 업데이트
                    else nextColCnt = Math.max(nextColCnt, idx);
                    
                    for (Point p : sortList) {
                        p.cnt = 0; // 초기화 작업
                        p.in = false; // 초기화 작업
                    }
                }
            } 
            
            else {
                for (int col = 1; col <= colCnt; col++) {
                    List<Point> sortList = new ArrayList<>();

                    for (int row = 1; row <= rowCnt; row++) {
                        int value = map[row][col]; // map에 저장된 값
                        if (value == 0) continue;
                        Point p = points[value];

                        p.cnt++;
                        if (!p.in) {
                            p.in = true;
                            sortList.add(p);
                        }
                    }

                    sortList.sort(Comparator.comparing((Point po) -> po.cnt)
                            .thenComparing(po -> po.num));

                    int idx = 1;
                    for (Point p : sortList) {
                        if (idx >= 101) break;
                        map[idx][col] = p.num; // 먼저 1번 인덱스 수
                        map[++idx][col] = p.cnt; // 그 다음 인덱스로 cnt
                        idx++; // idx 증가시키기
                    }

                    for (int row = idx; row < 101; row++) {
                        map[row][col] = 0; // 남아있는 열은 모두 0으로 설정하기
                    }

                    if (col == 1) nextRowCnt = idx; // 변경된 col 개수 업데이트
                    else nextRowCnt = Math.max(nextRowCnt, idx);

                    for (Point p : sortList) {
                        p.cnt = 0; // 초기화 작업
                        p.in = false; // 초기화 작업
                    }
                }
            }

            rowCnt = nextRowCnt;
            colCnt = nextColCnt;

            time++;
        }
    }
    
    int getTime() {
        return time <= 100 ? time : -1; // 100 이하라면 그대로, 101이 된다면 -1
    }
    
    static class Point {
        int num; // point 번호 (숫자)
        int cnt; // 숫자가 행 혹은 열에 나온 갯수
        boolean in; // 리스트에 있는지 없는지 판단
        
        Point (int num) {
            this.num = num;
        }
    }
}

2. 풀이 중점 사항

먼저, 해당 문제는 행과 열을 비교하고 정렬하는 과정이 필요했고, 0.5초의 짧은 시간제한이 있기 때문에 시간 복잡도를 계산하는 과정이 필요했습니다.

time은 최대 100, 행 최대 100, 열 최대 100 이므로 약 100만입니다. O(k * n * m) 

arrayList를 생성하여 값을 추가한 후 정렬하는 과정을 생각하였을 때,

sort 정렬은 TimSort 기준으로 O(nlogn)이고 n은 최대 100입니다. (모든 숫자가 전부 다를 수 있으므로)

따라서, O(k * n * m + k * n * m logm) => O(k * n * m log m)이라고 볼 수 있기에

약 200만 정도의 시간 복잡도를 가진다고 볼 수 있습니다.

1초당 약 1억개의 연산이므로 0.5초는 대략 5000만 개 정도의 연산을 할 수 있다고 생각하면 while 루프 내부에서 이중 for문과 정렬을 활용한 방법을 사용한다면 시간 내에 해결할 수 있을 것이라고 판단하였습니다.

Point[] points = new Point[101];
    
ArrayCalculation (int r, int c, int k) {
    this.r = r;
    this.c = c;
    this.k = k;

    for (int i = 1; i <= 100; i++) points[i] = new Point(i); // 포인트 초기화
}

핵심은 행에 있는 각 컬럼들의 숫자의 개수에 따라 정렬을 해야 하는 것입니다. 이 문제를 해결하기 위해,
Point를 담은 point 배열을 선언하였고 미리 초기화 하였습니다.

if (rowCnt >= colCnt) { // 행이 열보다 같거나 긴 경우
    for (int row = 1; row <= rowCnt; row++) {
        List<Point> sortList = new ArrayList<>();
        
        for (int col = 1; col <= colCnt; col++) {
            int value = map[row][col]; // map에 저장된 값

            if (value == 0) continue;
            Point p = points[value];

            p.cnt++;
            if (!p.in) { // 만약 p가 리스트에 없다면
                p.in = true; // 리스트에 있다는 표시
                sortList.add(p); // 리스트 추가
            }
        }

만약 p.in 이 false라면, 아직 정렬을 위한 리스트에 추가되지 않은 것이라고 판단하여 p.in = true로 표시한 후 sortList에 추가하였습니다.

sortList.sort(Comparator.comparing((Point po) -> po.cnt)
        .thenComparing(po -> po.num));

int idx = 1;
for (Point p : sortList) {
    if (idx >= 101) break;
    map[row][idx] = p.num; // 먼저 1번 인덱스 수
    map[row][++idx] = p.cnt; // 그 다음 인덱스로 cnt
    idx++; // idx 증가시키기
}

for (int col = idx; col < 101; col++) {
    map[row][col] = 0; // 남아있는 열은 모두 0으로 설정하기
}

Comporator.comparing().thenComparing()을 활용하여, 문제 상황에 맞도록 숫자의 개수로 오름차순 정렬, 숫자 개수가 같다면 숫자로 오름차순 하여 정렬하였습니다.

sortList를 순회하여 idx를 설정하여 num, cnt 순서 다시 2차원 배열 map에 추가하였습니다.

idx는 num, cnt로 설정되며 만약 100 이전에 끝난다면 하단의 for문이 실행되고, 101이 되어 종료된 것이라면 하단 for문은 col < 101을 만족하지 않게 됩니다.

if (row == 1) nextColCnt = idx; // 변경된 col 개수 업데이트
else nextColCnt = Math.max(nextColCnt, idx);

for (Point p : sortList) {
    p.cnt = 0; // 초기화 작업
    p.in = false; // 초기화 작업
}

앞 서 nextRowCnt, nextColCnt를 선언한 이유는 한 번의 while문이 실행된 후 루프를 돌 때, rowCnt, colCnt를 업데이트하기 위함입니다. 해당 로직은 for(int row = 1 ~ ) 내부에 있기 때문에, rowCnt 혹은 colCnt를 바꿔버리면 다음 행에 영향을 주게 됩니다. 한 행에 대한 로직을 마쳤으므로 sortList에서 Point 인스턴스를 순회하며 다시 초기화해주었습니다.

이상으로 백준 이차원 배열과 연산 자바 풀이를 마치도록 하겠습니다. 감사합니다.!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출 낚시왕 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/17143

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = parseInt(st.nextToken());
        int c = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
    
        Fishing fishing = new Fishing(r, c);
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            fishing.setMap(parseInt(st.nextToken()), parseInt(st.nextToken())
                    ,parseInt(st.nextToken()), parseInt(st.nextToken())
                    ,parseInt(st.nextToken()));
        }
        
        fishing.start();
        System.out.println(fishing.getAmount());
    }
}

class Fishing {
    int amount;
    int n; // 행 개수
    int m; // 열 개수 (시작 , 열 , 끝) -> m + 2
     
    Shark[][][] map;
    List<Shark> sharks = new LinkedList<>();
    
    Fishing (int n, int m) {
        this.n = n;
        this.m = m;
        map = new Shark[2][n + 1][m + 2];
    }

    void setMap(int row, int col, int speed, int dir, int size) { // row = 1, col = 1 부터 시작
        Shark shark = new Shark(row, col, speed, dir, size);
        map[0][row][col] = shark;
        sharks.add(shark);
    }
    
    void start() {
        int king = 0; // 낚시왕 위치 (0번 열)
        while (king < m + 1) { // 낚시 왕이 마지막 인덱스에 도달할 때까지 
            king++; // 낚시왕 한칸 이동
            
            for(int row = 1; row <= n; row++) {
                if (map[0][row][king] != null) { // 만약 왕의 위치에 상어가 있다면
                    Shark shark = map[0][row][king];
                    amount += shark.size;
                    map[0][row][king] = null; // 상어 참조 끊기
                    sharks.remove(shark); // 상어 제거
                    break;
                }
            }
            
            // 상어 이동하기 모두 이동을 마친 후 잡아먹을 수 있음
            for (Shark shark : sharks) move(shark);

            sharks = new LinkedList<>();
            for (int row = 1; row <= n; row++) {
                for (int col = 1; col <= m; col++) {
                    if (map[1][row][col] != null) {
                        map[0][row][col] = map[1][row][col];
                        map[1][row][col] = null;
                        sharks.add(map[0][row][col]);
                    }
                }
            }
        }
    }
    
    void move(Shark shark) {
        int nowRow = shark.row;
        int nowCol = shark.col;

        int nextRow = nowRow;
        int nextCol = nowCol;

        int dir = shark.dir; // 1: 위, 2: 아래, 3: 오른, 4: 왼
        int remain = shark.speed; // 상어가 일초동안 이동해야하는 크기;

        if (dir == 1 || dir == 2) { // 위로 이동이므로 row를 -- 아래로 이동은 row++
            while (remain > 0) { // 남아 있는 양
                if (nextRow == 1 && dir == 1) dir = 2;
                else if (nextRow == n && dir == 2) dir = 1;
                if (dir == 1) nextRow--;
                else nextRow++;
                remain--; // 남은 것 감소시키기
            }
        }

        else if (dir == 3 || dir == 4) {
            while (remain > 0) { // 남아 있는 양
                if (nextCol == 1 && dir == 4) dir = 3;
                else if (nextCol == m && dir == 3) dir = 4;
                if (dir == 3) nextCol++;
                else nextCol--;
                remain--; // 남은 것 감소시키기
            }
        }

        shark.row = nextRow; // 모든 이동 마침 (상어 업데이트)
        shark.col = nextCol;
        shark.dir = dir;
        map[0][nowRow][nowCol] = null; // 기존에 있던 위치 참조 제거하기

        if (map[1][nextRow][nextCol] != null) {
            Shark nowShark = map[1][nextRow][nextCol];
            if (nowShark.size < shark.size) map[1][nextRow][nextCol] = shark;
        } else map[1][nextRow][nextCol] = shark; // 상어 위치 업데이트 하기
    }
    
    int getAmount() {
        return amount;
    }

    static class Shark {
        int row;
        int col;
        int speed;
        int dir;
        int size;
        
        Shark (int row, int col, int speed, int dir, int size) {
            this.row = row;
            this.col = col;
            this.speed = speed;
            this.dir = dir;
            this.size = size;
        }
    }
}

2. 풀이 중점 사항

이번 문제는 3차원 배열로 선언하여, 참조를 설정하고 끊는 방법으로 문제를 해결할 수 있었습니다.

if (dir == 1 || dir == 2) { // 위로 이동이므로 row를 -- 아래로 이동은 row++
    while (remain > 0) { // 남아 있는 양
        if (nextRow == 1 && dir == 1) dir = 2;
        else if (nextRow == n && dir == 2) dir = 1;
        if (dir == 1) nextRow--;
        else nextRow++;
        remain--; // 남은 것 감소시키기
    }
}

헷갈릴 수 있는 부분은 1 혹은 n, m에 도착했을 때 dir을 바꿔주어야 한다는 점입니다.

만약 상어가 row 1에 도착했을 때, dir = 1이라면 더 row-- 할 없습니다. 이 때는,

dir = 2로 변경하여 row++로 바꿔서 진행할 수 있도록 해야 합니다.

모든 상어의 이동이 멈춘 후, 업데이트를 진행해야 하므로 새롭게 위치한 상어는 3차원 배열의 1차원 배열 인덱스 1에 처리하였고, 
1차원 배열의 1번 인덱스는 업데이트 되는 상어의 위치므로 만약 이미 존재하는 상어가 있다면 크기를 비교해서 없애거나, 살리는 방법을 적용하였습니다.

sharks = new LinkedList<>();
for (int row = 1; row <= n; row++) {
    for (int col = 1; col <= m; col++) {
        if (map[1][row][col] != null) { // 있다면 상어 이동 후 살아있는 상어
            map[0][row][col] = map[1][row][col]; // 0으로 옮겨준 후
            map[1][row][col] = null; // 참조 제거
            sharks.add(map[0][row][col]); // 다음 while을 위해 추가
        }
    }
}

업데이트 시 살아있는 상어는 1차원 배열 0번째 인덱스로 옮겨서 다음 while이 작동될 수 있도록 하였습니다.

자세한 풀이는 주석처리하였습니다. 이상으로 낚시왕 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 미세먼지 안녕! 자바 풀이를 진행하고자 합니다.!

문제 출처: https://www.acmicpc.net/problem/17144

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int r = parseInt(st.nextToken());
        int c = parseInt(st.nextToken());
        int t = parseInt(st.nextToken());

        AirCleaner airCleaner = new AirCleaner(r, c, t); // 공기 청정기 설정

        for (int row = 0; row < r; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < c; col++) {
                airCleaner.setMap(row, col, parseInt(st.nextToken()));
            }
        }

        airCleaner.on();
        System.out.println(airCleaner.getDusty());
    }
}

class AirCleaner {

    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};

    int n; // 공기 청정기 행 길이
    int m; // 공기 청정기 열 길이
    int time; // 작동해야 하는 시간
    int[][][] map; // 0: 현재 값, 1: 업데이트에 적용될 확산 저장
    List<Point> cleaner = new ArrayList<>(); // 공기청정기는 2n (n은 1 이상)

    AirCleaner(int n, int m, int time) {
        this.n = n;
        this.m = m;
        this.time = time;

        map = new int[2][n][m];
    }

    void setMap(int row, int col, int value) {
        map[0][row][col] = value;
        if (value == -1) cleaner.add(new Point(row, col)); // 클리너 포인트 저장하기
    }

    void on() {
        int localTime = 0; // 지역변수 설정

        while (localTime < time) {

            for (int row = 0; row < n; row++) {
                for (int col = 0; col < m; col++) {

                    if (map[0][row][col] == 0) continue;

                    int count = 0; // 확산 가능한 개수 정하기
                    for (int k = 0; k < 4; k++) {
                        int nextR = row + DR[k];
                        int nextC = col + DC[k];
                        if (!isValid(nextR, nextC)) continue;
                        count++;
                    }

                    int diffusion = map[0][row][col] / 5; // 문제 공식에 의한 확산량 설정
                    map[0][row][col] -= diffusion * count; // 문제 공식에 의한 확산하게 한 먼지 업데이트

                    for (int k = 0; k < 4; k++) {
                        int nextR = row + DR[k];
                        int nextC = col + DC[k];
                        if (!isValid(nextR, nextC)) continue;
                        map[1][nextR][nextC] += diffusion; // 확산된 먼지를 받은 곳 업데이트
                    }
                }
            } // 확산시키기

            for (int row = 0; row < n; row++) {
                for (int col = 0; col < m; col++) {
                    map[0][row][col] += map[1][row][col];
                    map[1][row][col] = 0;
                }
            } // 확산한 값 추가하기 (모두 한 번에 확산되기 때문에 1차원 1인덱스 배열에 추가한 값 업데이트 실시

            // 청정기 작동
            for (int i = 0; i < cleaner.size(); i++) {
                Point p = cleaner.get(i);
                int pRow = p.row; // pRow = 0 아님
                int pCol = p.col; // pCol = 0 임

                if (i % 2 == 0) { // 짝수번은 위로
                    pRow -= 1; // 한칸 위로 먼저 올리기

                    while(pRow > 0) { // pRow가 0보다 클 때까지 한칸 내리기
                        map[0][pRow][pCol] = map[0][pRow - 1][pCol]; // 한칸씩 이동
                        pRow--; // 한칸 이동 시킨 후 위로 다시 올리기
                    }

                    while (pCol < m - 1) { // pCol이 m - 1보다 작을 때까지 --> pCol이 m - 1에 도달 종료
                        map[0][pRow][pCol] = map[0][pRow][pCol + 1];
                        pCol++;
                    }

                    while (pRow < p.row) { // pRow가 p.row보다 작을 때까지 내리면서 업데이트
                        map[0][pRow][pCol] = map[0][pRow + 1][pCol];
                        pRow++;
                    }

                    while(pCol > 1) { // pRow == 0, pCol > 0일 때까지 감소
                        map[0][pRow][pCol] = map[0][pRow][pCol - 1];
                        pCol--;
                    }
                    map[0][p.row][p.col + 1] = 0;
                }

                else { // 홀수번은 아래로 순회
                    pRow += 1; // 한칸 아래로 내리기

                    while(pRow < n - 1) { // pRow가 n - 1보다 작을 때까지 한칸 내리기
                        map[0][pRow][pCol] = map[0][pRow + 1][pCol]; // 한칸씩 이동
                        pRow++; // 한칸 이동 시킨 후 위로 다시 올리기
                    }

                    while (pCol < m - 1) { // pCol이 m - 1보다 작을 때까지 --> pCol이 m - 1에 도달 종료
                        map[0][pRow][pCol] = map[0][pRow][pCol + 1];
                        pCol++;
                    }

                    while (pRow > p.row) { // pRow가 p.row보다 작을 때까지 내리면서 업데이트
                        map[0][pRow][pCol] = map[0][pRow - 1][pCol];
                        pRow--;
                    }

                    while(pCol > 1) { // pRow == 0, pCol > 0일 때까지 감소
                        map[0][pRow][pCol] = map[0][pRow][pCol - 1];
                        pCol--;
                    }
                    map[0][p.row][p.col + 1] = 0;
                }
            }
            localTime++;
        }
    }

    boolean isValid(int row, int col) { // 유효한 인덱스에 공기 청정기가 아니여야 함
        return row >= 0 && row < n && col >= 0 && col < m &&
                map[0][row][col] != -1;
    }

    int getDusty() {
        int amount = 0; // 공기청정기 및 0을 제외한 양수값 추가
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                if (map[0][row][col] > 0) amount += map[0][row][col];
            }
        }
        return amount;
    }

    static class Point {
        int row;
        int col;

        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

2. 풀이 중점 사항

반시계, 시계 방향 회전하기

문제가 길면 중요한 단서를 놓이게 되는 문제가 발생할 수 있습니다. 공기청정기는 1초에 한 칸씩 미는 작업을 수행합니다. 

공기청정기는 같은 열에 특정 행의 위아래 인접하여 있기 때문에, 먼저 들어오는 공기청정기는 반시계 방방, 그다음 공기청정기는 시계방향으로 회전하게 됩니다.

한 칸씩 미는 작업을 수행하기 위해 역순으로 처리하는 구현을 작성하여 해결할 수 있습니다.

예를 들어 공기 청정기 쪽으로 들어오는 먼지 순서가 1, 2, 3 일때,

3 -> 2로 업데이트, 2 -> 1로 업데이트 1 -> 0으로 업데이트하려면 2, 1을 담아놓을 swap 변수가 필요합니다

하지만, 2 -> 1, 3 -> 2 순으로 역순으로 처리하면 swap 변수를 할당하지 않아도 한 칸씩 밀 수 있습니다.

나머지 자세한 코드는 모두 주석으로 처리하였습니다.

이상으로 미세먼지 안녕 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 

이번 포스팅은 백준 SW 기출문제 - 아기 상어 자바 풀이를 진행하도록 하겠습니다.

해당 문제는 메모리 초과가 여러 번 발생하여, 여러 시도 끝에 해결할 수 있었던 문제입니다.

문제 출처: https://www.acmicpc.net/problem/16236

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        
        BabyShark shark = new BabyShark(n);
        
        for (int row = 0; row < n; row++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int col = 0; col < n; col++)
                shark.setMap(row, col, parseInt(st.nextToken()));
        }
        
        shark.eat();
        System.out.println(shark.getTime());
    }
}

class BabyShark {
    
    static final int[] DR = {-1, 0, 0, 1};
    static final int[] DC = {0, -1, 1, 0};
    
    int n;
    int[][] map;
    int visitedCount;
    int[][] visited;
    int time;
    Shark shark;
    
    BabyShark(int n) {
        this.n = n;
        map = new int[n][n]; // n by n;
        visited = new int[n][n]; // 방문 여부를 int type으로 처리 참조 #1
    }
    
    void setMap(int row, int col, int value) {      
        if (value == 9) shark = new Shark(row, col, 2, 0);
        else if (value != 0) {
            map[row][col] = value;
        }
    }
    
    void eat() {

        while (true) {
            Queue<Point> queue = new ArrayDeque<>(); // queue는 point를 입력하여 가장 가까운 거리를 찾기 위한 용도
            queue.add(new Point(shark.row, shark.col, 0)); // 현재 위치한 상어 위치 설정
            Point fish = null; // 물고기 위치 초기화

            int minTime = Integer.MAX_VALUE; // 최소 시간 최대치로 초기화
            visitedCount++; // 방문한 개수 ++
            visited[shark.row][shark.col] = visitedCount; // 방문처리 (매번 boolean[][]을 생성하거나 false로 초기화 하는 것을 방지 )

            while(!queue.isEmpty()) {
                Point point = queue.poll();

                int row = point.row; 
                int col = point.col;

                if (minTime < point.time) break; // 만약 최소 시간보다 큰 순간부터는 큐의 성질에 의해 time은 현재 타임과 같거나 크게 됨 따라서 종료
                
                if (map[row][col] != 0 && map[row][col] < shark.level) { // 0이 아니면서 상어가 먹을 수 있는 물고기 존재
                    if (fish == null) { // fish에 값이 없다면
                        fish = point;
                        minTime = Math.abs(fish.row - shark.row) + Math.abs(fish.col - shark.col);
                    } else { // fish에 값이 있다면 업데이트 가능 여부 판단
                      if (fish.row > point.row || fish.row == point.row && fish.col > point.col) { // 더 행이 높은 곳에 있거나 (row가 더 작은 것 ), 두 행의 높이가 같다면 더 왼쪽에 가까운  것(col이 더 작은 것)
                          fish = point;
                      }
                    }
                }

                for (int k = 0; k < 4; k++) {
                    int nextR = row + DR[k];
                    int nextC = col + DC[k];

                    if (!isValid(nextR, nextC)) continue; // 유효한 인덱스 X, 물고기가 더 클 때,  visitedCount 같다면 continue
                    queue.add(new Point(nextR, nextC, point.time + 1));
                    visited[nextR][nextC] = visitedCount; // 방문 여부를 visitedCount로 설정함으로써, 방문 여부를 체크하는 것
                }
            }
            
            if (fish == null) break; // 만약 더 이상 물고기가 없다면 종료

            time += fish.time; // 물고기 찾는데 걸린 시간 추가하기
            shark.eatenCnt++; // 상어가 먹은 개수 업데이트
            map[fish.row][fish.col] = 0; // 먹은 물고기 없애기

            shark.row = fish.row; // 물고기 위치로 상어 업데이트
            shark.col = fish.col;
            
            if (shark.eatenCnt == shark.level) { // 만약 먹은 개수와 상어 레벨이 같다면
                shark.level++; // 상어 레벨 업데이트
                shark.eatenCnt = 0; // 먹은 개수 0 초기화
            }
        }

    }
    
    // 유효한 범위 && 물고기가 상어보다 작고 방문 안한 경우 (인트 값이 다른 경우)
    boolean isValid(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < n
            && map[row][col] <= shark.level && visited[row][col] != visitedCount;
    }
    
    int getTime() {
        return time;
    }
    
    static class Shark {
        int row;
        int col;
        int level;
        int eatenCnt;
        
        Shark (int row, int col, int level, int eatenCnt) {
            this.row = row;
            this.col = col;
            this.level = level;
            this.eatenCnt = eatenCnt;
        }
    }
    
    static class Point {
        int row;
        int col;
        int time;

        Point(int row, int col, int time) {
            this.row = row;
            this.col = col;
            this.time = time;
        }
    }
}

2. 풀이 중점 사항 

시간 복잡도 측면에서, n은 최대 20입니다.

n by n 행렬이므로 20 ^ 2 입니다.

BFS의 시간 복잡도는 O(v + e) (v 정점, e 간선)의 개수이므로n^2 + 4(상하좌우) * n^2 (정점의 개수) -> O(n^2)이 처리되게 됩니다.

일반적인 BFS에, 물고기가 있는 위치에 가서 물고기를 먹고 다시 물고기를 탐색해야하므로, 물고기의 개수  n*n개를 추가로 곱하면  O(n^4) 입니다. n = 20이므로 16만입니다.

약 1초당 1억번 연산이 가능하다고 하므로, 안정적으로 시간 복잡도는 통과할 수 있었습니다.

참고 #1

처음에 저는 방문 여부를 true로 표시하고, queue가 종료되어 다시 while 루프를 돌아야 할 때,
visited를 false로 초기화하는 코드를 작성하였습니다.

하지만, 그 결과 계속 메모리 초과가 발생하여, int형으로 수정한 후 방문 개수를 업데이트하여 boolean의 2차원 배열을 
생성하거나 혹은 초기화하는 작업을 제거할 수 있었습니다.

이를 통해 메모리 초과 문제를 해결할 수 있었습니다.

visitedCount 원리는 true와 비슷하게, 만약 현재 방문한 곳이 visitedCount값이 아니라면, 방문하지 않은 것이므로
visitedCount로 업데이트하고 큐에 넣어주는 것입니다. 이를 통해 방문 처리를 간소화할 수 있습니다.

참고 #2

테스트의 예제 입력 6에서 60이 아닌 56이 계속 나와서 디버깅을 찍고 위치가 이동하는 것을 파악하였습니다.

너무 단순하게 당연히 행이 높은 것, 가장 왼쪽인 것 부터 순회하도록 DR, DC를 작성하였기 때문에 먼저 가장 빠르게 물고기를 찾는다면 while(! queue.isEmpty())를 break 하였습니다.

static final int[] DR = {-1, 0, 0, 1};
static final int[] DC = {0, -1, 1, 0};

하지만, 이것은 엄청난 큰 실수로 다음의 반례를 생각해볼 수 있었습니다.

0 0 0 0 9 0 0 1
0 0 1 0 0 0 0 0

원래의 정답이라면 (0, 7)에 있는 물고기를 먼저 먹어야 하지만,

DR, DC로 순회하여 단순하게 먼저 찾는 로직을 구성하도록 작성한다면

왼쪽이 오른쪽보다 더 우선순위가 있으므로 큐는 (1, 2)의 물고기가 먼저 poll 되게 됩니다.

따라서, 오답이 되게 됩니다.

이 문제를 해결하기 위해서는 물고기를 찾는 minTime을 설정하고 minTime보다 크게 되는 순간은 
큐 성질에 의해 time보다 큰 성질을 유지하게 되므로, 종료 시킵니다.

만약 같은 경우에는 행이 더 높은지 (row가 0에 가까운지) , 만약 동일하다면 왼쪽에 있는지(col이 0에 가까운지)를 판단하여 문제를 해결해야 했습니다.

한 순간에 착각이 큰 문제가 될 수 있었습니다.

이상으로 아기 상어 자바 풀이를 마치겠습니다. 감사합니다.!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 - 나무 재테크 자바 풀이를 작성하고자 합니다.

제가 제일 좋아하는 우선순위 큐 스케줄링 유형으로 정말 재밌게 풀었던 것 같습니다.

문제 출처: https://www.acmicpc.net/problem/16235

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());
        
        TreeInvestment treeInvestment = new TreeInvestment(n, k);
        
        for (int row = 1; row <= n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= n; col++)
                treeInvestment.setNutrientMap(row, col, parseInt(st.nextToken())); // 영양분 초기화
        }
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            treeInvestment.setTrees(parseInt(st.nextToken()), parseInt(st.nextToken()), parseInt(st.nextToken())); // 트리 추가
        }
        
        treeInvestment.start();
        System.out.println(treeInvestment.getAlive());
    }    
}

class TreeInvestment {
    
    static final int[] DR = {-1, -1, -1, 0, 0, 1, 1, 1}; // 8개 방향 설정
    static final int[] DC = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    int n; // n + 1 by n + 1 행렬
    int k; // k년 후
    int[][][] nutrientMap; // 영양분 맵
    PriorityQueue<Tree> springQueue = new PriorityQueue<>(Comparator.comparing((Tree tr) -> tr.age)); // 봄에 살아 있는 나무  우선순위 큐
    Queue<Tree> autumnQueue = new ArrayDeque<>(); // 가을에 살아 있는 나무 큐
    Queue<Tree> summerQueue = new ArrayDeque<>(); // 여름 큐 (죽은 나무 영양분을 위해)
    
    TreeInvestment(int n, int k) {
        this.n = n;
        this.k = k;
        
        nutrientMap = new int[2][n + 1][n + 1]; // 3차원 배열의 1차원 --> 0: 현재, 1: 매년 추가되는 양분의 양
       
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= n; col++) {
                nutrientMap[0][row][col] = 5;  // 5 초기화
            }
        }
    }
    
    void setNutrientMap(int row, int col, int value) {
        nutrientMap[1][row][col] = value; // 매년 추가되는 양분의 양 초기화
    }
    
    void setTrees(int row, int col, int age) {
        springQueue.add(new Tree(row, col, age)); // 트리 스프링큐에 추가하기 
    }
    
    void start() {
        int nowK = 0; // 0년 째
        
        while (nowK < k) {
            while(!springQueue.isEmpty()) { // 봄          
                Tree tree = springQueue.poll();
                int row = tree.row;
                int col = tree.col;

                if (nutrientMap[0][row][col] >= tree.age) {
                    nutrientMap[0][row][col] -= tree.age; // 나이만큼 양분 제거
                    tree.age++; // 나이 ++
                    autumnQueue.add(tree); // 다음 큐에 추가 (내년에도 살아 있게 됨)
                } 
                
                else summerQueue.add(tree); // 여름에 양분 추가를 위해 여름큐 등록
            }
            
            while (!summerQueue.isEmpty()) { // 여름 양분 등록하기 
                Tree tree = summerQueue.poll();
                nutrientMap[0][tree.row][tree.col] += tree.age / 2; // 죽은 나무는 나이 / 2의 양만큼 영양분
            }
            
            while(!autumnQueue.isEmpty()) { // 가을
                Tree tree = autumnQueue.poll();
                
                if (tree.age % 5 == 0) { // 5의 배수는 번식
                    
                    for (int k = 0; k < 8; k++) {
                        int nextR = tree.row + DR[k];
                        int nextC = tree.col + DC[k];
                        
                        if (!isValid(nextR, nextC)) continue;
                        springQueue.add(new Tree(nextR, nextC, 1)); // 나무가 생긴 것은 springQueue에 등록
                    }
                }
                springQueue.add(tree); // 번식한 트리도 queue에 추가
            }
            
            for (int row = 1; row <= n; row++) { // 겨울은 양분을 추가함
                for (int col = 1; col <= n; col++) 
                    nutrientMap[0][row][col] += nutrientMap[1][row][col];
            }
            
            nowK++; // 1년이 지남
        }
        
    }
    
    int getAlive() { // k년뒤에도 살아있다는 것은 springQueue에 있다는 것을 의미
        return springQueue.size();
    }
    
    boolean isValid (int row, int col) {
        return row > 0 && row <= n && col > 0 && col <= n; // 1, 1 시작이므로
    }
    
    static class Tree {
        int row;
        int col;
        int age;
        
        Tree (int row, int col, int age) {
            this.row = row;
            this.col = col;
            this.age = age;
        }
    }
}

2. 풀이 중점 사항

이번 문제는 봄, 여름, 가을, 겨울 각 상황에 따라 나무가 죽거나 살고, 영양분이 추가되는 일련의 과정을 하나의 스케줄링으로 처리하는 과정이 필요했습니다.

int n; // n + 1 by n + 1 행렬
int k; // k년 후
int[][][] nutrientMap; // 영양분 맵
PriorityQueue<Tree> springQueue = new PriorityQueue<>(Comparator.comparing((Tree tr) -> tr.age)); // 봄에 살아 있는 나무  우선순위 큐
Queue<Tree> autumnQueue = new ArrayDeque<>(); // 가을에 살아 있는 나무  우선순위 큐
Queue<Tree> summerQueue = new ArrayDeque<>(); // 여름 큐 (죽은 나무 영양분을 위해)

양분은 현재 있는 양분과 겨울에 추가되는 양분을 구분하기 위해 3차원 배열로 선언하여 1차원의 0번째 인덱스는 현재 양분의 양,

1번 인덱스는 겨울에 추가되는 양분의 양을 기록하였습니다.

봄, 여름, 가을에 대해 각각 우선순위 큐, 큐, 큐를 적용하여 봄에 살아 있는 나무, 죽어서 여름에 양분이 되는 나무, 가을에 살아서 번식하는 나무를 큐에 추가할 수 있도록 설정하였습니다.

나무의 나이가 적은 순서대로 먼저 양분을 획득하도록 해야 하므로 봄은 우선순위 큐로 적용하였습니다. 

    while(!springQueue.isEmpty()) { // 봄          
        Tree tree = springQueue.poll();
        int row = tree.row;
        int col = tree.col;

        if (nutrientMap[0][row][col] >= tree.age) {
            nutrientMap[0][row][col] -= tree.age; // 나이만큼 양분 제거
            tree.age++; // 나이 ++
            autumnQueue.add(tree); // 다음 큐에 추가 (내년에도 살아 있게 됨)
        } 

        else summerQueue.add(tree); // 여름에 양분 추가를 위해 여름큐 등록
    }

    while (!summerQueue.isEmpty()) { // 여름 양분 등록하기 
        Tree tree = summerQueue.poll();
        nutrientMap[0][tree.row][tree.col] += tree.age / 2; // 죽은 나무는 나이 / 2의 양만큼 영양분
    }

중점사항은, 죽은 나무는 springQueue에 있는 모든 나무가 처리된 이후 양분으로 추가해야 합니다. 왜냐하면, 봄 -> 여름이라는 스케줄이 있기 때문에 죽었다고 해서 바로 양분으로 처리하면, 답이 다르게 처리될 수 있습니다.

while(!autumnQueue.isEmpty()) { // 가을
    Tree tree = autumnQueue.poll();

    if (tree.age % 5 == 0) { // 5의 배수는 번식

        for (int k = 0; k < 8; k++) {
            int nextR = tree.row + DR[k];
            int nextC = tree.col + DC[k];

            if (!isValid(nextR, nextC)) continue;
            springQueue.add(new Tree(nextR, nextC, 1)); // 나무가 생긴 것은 springQueue에 등록
        }
    }
    springQueue.add(tree); // 번식한 트리도 queue에 추가
}

for (int row = 1; row <= n; row++) { // 겨울은 양분을 추가함
    for (int col = 1; col <= n; col++) 
        nutrientMap[0][row][col] += nutrientMap[1][row][col];
}

nowK++; // 1년이 지남

가을에서 번식에 성공을 마치고 나면 봄 우선순위 큐에 다시 추가하여, 봄에도 살아있을 수  있도록 처리하였습니다.

겨울은 양분을 추가하였고 겨울까지 마친 후 nowK++로 1년이 지나도록 설정하였습니다.

이상으로 나무 재테크 자바 풀이를 마치도록 하겠습니다.

감사합니다.!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 인구 이동 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/16234

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = parseInt(st.nextToken());
        int L = parseInt(st.nextToken());
        int R = parseInt(st.nextToken());
        
        PeopleMove pm = new PeopleMove(N, L, R);
        
        for (int row = 0; row < N; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < N; col++) {
                pm.setMap(row, col, parseInt(st.nextToken()));
            }
        }
        
        pm.run();
        System.out.println(pm.getDays());
    }
}

class PeopleMove {
    
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};
    
    int n; //  n by n 행렬
    int low; // 인구 차이 R 이하의 R
    int high; // 인구 차이 L 이상의 L
    int[][] map;
    int result; // 결과
    int currentPeopleCnt; // dfs  로얻은 현재 인구 수
    List<Point> current; // 현재 dfs에 적용할 때, 인구 이동해야하는 포인트
    boolean[][] visited; // 방문
    
    PeopleMove (int n, int low, int high) {
        map = new int[n][n];
        visited = new boolean[n][n];
        
        this.n = n;
        this.low = low;
        this.high = high;
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }
    
    void run() {
        
        while(true) {
            int breakPoint = 0; // 만약 current.size() == 1 이라면 (인구 이동 X) breakPoint++ 하여 n * n 개수와 같은지 판단
            for (int row = 0; row < n; row++) {
                for (int col = 0; col < n; col++) {
                    current = new ArrayList<>(); // dfs에 적용할 current 리스트
                    currentPeopleCnt = 0; // 0 초기화
                    dfs(row, col); // dfs
                    
                    // 국경선이 닫힌 것이므로 이제 인구이동 시작하기 
                    if (current.size() > 1) {
                        int avgPeopleCnt = currentPeopleCnt / current.size();
                        for (Point p : current) map[p.row][p.col] = avgPeopleCnt; // 인구 평균으로 업데이트
                    } else breakPoint++; // 만약 모든 dfs가 하나씩만 나오게 되는 경우
                }
            }

            
            if (breakPoint == n * n) break; // 인구 이동할 수 없으므로 종료
            result++; // 인구 이동 가능하므로 횟수 ++
            for (int row = 0; row < n; row++) Arrays.fill(visited[row], false); //dfs 결과 초기화
        }
    }

    void dfs(int row, int col) {
 
        if (visited[row][col]) return; // 만약 방문한 경우 return
        visited[row][col] = true; // 방문 표시
        
        currentPeopleCnt += map[row][col]; // currentPeopleCnt 전역변수에 ++
        current.add(new Point(row, col)); // current 리스트에 추가
        
        for (int k = 0; k < 4; k++) {
            int nextR = row + DR[k];
            int nextC = col + DC[k];
            if (!isValid(row, col, nextR, nextC)) continue;
            dfs(nextR, nextC); // 재귀
        }
    }
    
    // 현재 행, 열 --- 지금 행, 열 비교 인덱스 유효하고, 인접한 두 좌표가 low <= 차이 <= high 여야 함
    boolean isValid(int preRow, int preCol, int nowRow, int nowCol) {
        return nowRow >= 0 && nowRow < n && nowCol >= 0 && nowCol < n 
            && Math.abs(map[preRow][preCol] - map[nowRow][nowCol]) <= high
            && Math.abs(map[preRow][preCol] - map[nowRow][nowCol]) >= low;
    }
    
    int getDays() {
        return result;
    }
    
    static class Point {
        int row;
        int col;
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

2. 풀이 중점 사항

해당 문제는 2차원 포문에서 인구 이동이 가능한 그룹 하나당 result++가 아니라,

2중 포문이 모두 종료되어 인구 이동이 가능한 그룹의 리스트들이 모두 처리된 후가 result++입니다.

void run() {

    while(true) {
        int breakPoint = 0; // 만약 current.size() == 1 이라면 (인구 이동 X) breakPoint++ 하여 n * n 개수와 같은지 판단
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                current = new ArrayList<>(); // dfs에 적용할 current 리스트
                currentPeopleCnt = 0; // 0 초기화
                dfs(row, col); // dfs

                // 국경선이 닫힌 것이므로 이제 인구이동 시작하기 
                if (current.size() > 1) {
                    int avgPeopleCnt = currentPeopleCnt / current.size();
                    for (Point p : current) map[p.row][p.col] = avgPeopleCnt; // 인구 평균으로 업데이트
                } else breakPoint++; // 만약 모든 dfs가 하나씩만 나오게 되는 경우
            }
        }


        if (breakPoint == n * n) break; // 인구 이동할 수 없으므로 종료
        result++; // 인구 이동 가능하므로 횟수 ++
        for (int row = 0; row < n; row++) Arrays.fill(visited[row], false); //dfs 결과 초기화
    }
}

따라서, 위의 코드처럼 current.size()가 1보다 크다면, 즉 인구 이동이 가능한 도시가 있다면 인구 이동을 처리한 후, 

모든 탐색이 끝난 후 breakPoint를 확인 후 result를 업데이트하는 방식입니다.

void dfs(int row, int col) {

    if (visited[row][col]) return; // 만약 방문한 경우 return
    visited[row][col] = true; // 방문 표시

    currentPeopleCnt += map[row][col]; // currentPeopleCnt 전역변수에 ++
    current.add(new Point(row, col)); // current 리스트에 추가

    for (int k = 0; k < 4; k++) {
        int nextR = row + DR[k];
        int nextC = col + DC[k];
        if (!isValid(row, col, nextR, nextC)) continue;
        dfs(nextR, nextC); // 재귀
    }
}

dfs를 활용하여, 인접한 도시가 인구 이동이 가능하다면 재귀를 진행함으로써, 방문 여부를 체크할 수 있습니다. 

따라서, 2중 포문으로 방문 처리된 위치에 도착하더라도 이미 방문되었기 때문에 바로 return 하여 current.size() == 1을 유지할 수 있습니다.

만약 모든 도시가 인구 이동이 더 이상 불가능하다면 isValid()가 false가 되어 모든 도시는 전부 current.size() == 1이 되게 됩니다.

도시의 current.size() == 1이라면 breakPoint를 ++ 하므로, while문의 종료 조건을 만족할 수 있게 됩니다.

이상으로 인구 이동 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 치킨 배달 자바 풀이를 작성하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/15686

1. 풀이 소스

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        ChickenDistance chickenDistance = new ChickenDistance(n, m);
        
        for (int row = 1; row <= n; row++) { // 1행 1열 이므로
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= n; col++)
                chickenDistance.setMap(row, col, parseInt(st.nextToken()));
        }
        
        chickenDistance.start();
        
        System.out.println(chickenDistance.getMinDistance());
    }
}

class ChickenDistance {
    int n; // 정사각형 행렬
    int m; // m개의 선택된 치킨집
    boolean[] open; // 열려있는 집
    int minDistance = Integer.MAX_VALUE; // 최소 치킨 거리
    List<Point> chickens = new ArrayList<>(); // 치킨집 좌표
    List<Point> homes = new ArrayList<>(); // 집 좌표
    
    ChickenDistance(int n, int m) {
        this.n = n;
        this.m = m;
    }
    
    void setMap(int row, int col, int value) {
        if (value == 1) homes.add(new Point(row, col)); // 1이라면 집에 추가
        else if (value == 2) chickens.add(new Point(row, col)); // 2라면 치킨집 추가
    }
    
    void start() {
        open = new boolean[chickens.size()]; // 열려 있는집 초기화하기
        
        dfs(0, 0); // dfs
    }
    
    void dfs(int start, int cnt) {
        if (cnt == m) {            
            int minLocalDistance = 0; // 현재 dfs에서 지역변수 Distance 초기화  (모든 집이 거리 비교 끝나면 비교)

            for (Point home : homes) { // 집 리스트 순회
                int distance = Integer.MAX_VALUE; // 비교할 거리는 최대치로 초기화
                for (int i = 0; i < chickens.size(); i++) {
                    if (open[i]) { // 만약 열려 있다면
                        Point ch = chickens.get(i);
                        int nowD = Math.abs(home.row - ch.row) + Math.abs(home.col - ch.col);
                        distance = Math.min(nowD, distance); // 치킨집과 비교해서 거리 업데이트
                    }
                }
                minLocalDistance += distance;
            }
            
            minDistance = Math.min(minLocalDistance, minDistance);
            return;
        }
        
        for (int i = start; i < chickens.size(); i++) {
            open[i] = true; // 집 열려 있도록 설정
            dfs(i + 1, cnt + 1); // 다음 재귀로 조합 설정
            open[i] = false; // 백트래킹으로 다시 초기화함으로써, 다음 재귀에 영향 받지 않도록 설정
        }
    }
    
    int getMinDistance() {
        return minDistance;
    }
    
    static class Point {
        int row;
        int col;
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

2. 풀이 중점 사항

해당 문제는 백트래킹으로 해결하는 방법이 있습니다.

재귀를 수행할 때, m개의 치킨집을 선정한 후, 각 집에서 치킨집을 순회하며 거리를 측정해야 했습니다.

따라서, 먼저 백트래킹으로  치킨집을 여는 방법으로 m개의 조합이 설정될 수 있도록 하였습니다.

for (int i = start; i < chickens.size(); i++) {
    open[i] = true; // 집 열려 있도록 설정
    dfs(i + 1, cnt + 1); // 다음 재귀로 조합 설정
    open[i] = false; // 백트래킹으로 다시 초기화함으로써, 다음 재귀에 영향 받지 않도록 설정
}

만약 총 m개의 치킨집이 선택이 된다면 (open이 먼저 true가 되므로 총 m가 true)

int minLocalDistance = 0; // 현재 dfs에서 지역변수 Distance 초기화  (모든 집이 거리 비교 끝나면 비교)

for (Point home : homes) { // 집 리스트 순회
    int distance = Integer.MAX_VALUE; // 비교할 거리는 최대치로 초기화
    for (int i = 0; i < chickens.size(); i++) {
        if (open[i]) { // 만약 열려 있다면
            Point ch = chickens.get(i);
            int nowD = Math.abs(home.row - ch.row) + Math.abs(home.col - ch.col);
            distance = Math.min(nowD, distance); // 치킨집과 비교해서 거리 업데이트
        }
    }
    minLocalDistance += distance;
}

minDistance = Math.min(minLocalDistance, minDistance);
return;
}

minLocalDistance를 0으로 초기화한 후 집을 순회하며 가장 적은 거리의 치킨집을 업데이트합니다. 그리고, 하나의 집에 대한 치킨 거리가 업데이트되면, minLocalDistance에 최소 거리를 더하여 다음 집의 치킨 거리를 업데이트합니다.

이렇게 모든 집 업데이트가 끝나면, minDistance를 업데이트하고 return 합니다.

이어서 다음 재귀가 실행되고 cnt == m이되면 이와 같은 방법을 진행하되, 백트래킹으로 인해 다른 조합을 가진 오픈 치킨집이 설정되게 됩니다.

이상으로 치킨 거리 문제 풀이를 마치도록 하겠습니다.

감사합니다!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 드래곤 커브 자바 풀이를 진행하고자 합니다.

문제 출처:https://www.acmicpc.net/problem/15685

1. 풀이 소스:

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        
        DragonCurve curve = new DragonCurve();
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            curve.setMap(parseInt(st.nextToken()), parseInt(st.nextToken()),
                        parseInt(st.nextToken()), parseInt(st.nextToken()));
        }
        
        curve.build();
        System.out.println(curve.getSquare());
    }
}

class DragonCurve {
    boolean[][] map = new boolean[101][101]; // 0 ~ 100 까지 유효한 좌표로 드래곤 커브가 된 좌표
    List<Start> starts = new ArrayList<>(); // 드래곤 커브 시작점
    void setMap(int x, int y, int dir, int g) {
        starts.add(new Start(x, y, dir, g));
    }
    
    // 0: x++, 1: y--, 2: x--, 3: y++
    void build() {
        for (Start start : starts) {
            List<Point> nowPoints = new ArrayList<>(); // 드래곤 커브로 재귀 형태로 회전할 리스트
            nowPoints.add(new Point(start.x, start.y)); // 시작점 입력으로 추가
            map[start.x][start.y] = true; // 시작점 드래곤 커브에 true
            
            int referX = 0; // 90도 시계방향으로 회전시킬 기준점이 되는 x 좌표
            int referY = 0;
            
            switch (start.dir) {
                case 0:
                    referX = start.x + 1;
                    referY = start.y;
                    break;
                case 1:
                    referX = start.x;
                    referY = start.y - 1;
                    break;
                case 2:
                    referX = start.x - 1;
                    referY = start.y;
                    break;
                case 3:
                    referX = start.x;
                    referY = start.y + 1;
                    break;
            }
            map[referX][referY] = true;
            Point refer = new Point(referX, referY);
            nowPoints.add(refer);
            doCurve(1, start.g, nowPoints); // 재귀 실행
        }
    }
    
    // 특정 점을 기준으로 시계 방향 회전
    // x = a + (b - y)
    // y = b - (a - x)
    void doCurve(int k, int g, List<Point> nowPoints) { // 참조 #1
        if (k == g + 1) return; // 만약 드래곤 커브 세대가 끝이나면 종료 

        Point refer = nowPoints.get(nowPoints.size() - 1); // 마지막 입력은 모두 참조점이 됨 
        int prePointIdx = nowPoints.size() - 2; // 참조점을 제외하고 회전시킬 인덱스 (계속 리스트에 추가하므로 인트값을 설정 해야 함)
        for (int i = prePointIdx; i >= 0; i--) { // 내림차순 인덱스로 설정 참조 #2 
            Point p = nowPoints.get(i);
            int nextX = refer.x + (refer.y - p.y); // 공식 적용 
            int nextY = refer.y - (refer.x - p.x);
            map[nextX][nextY] = true;
            nowPoints.add(new Point(nextX, nextY)); // 다음 좌표 리스트에 추가 
        }

        doCurve(k + 1, g, nowPoints); // 재귀 실행 
    }
    
    int getSquare() {
        int result = 0;
        for (int row = 0; row < 100; row++) {
            for (int col = 0; col < 100; col++) {
                if (map[row][col] && map[row][col + 1] &&
                   map[row + 1][col] && map[row + 1][col + 1]) // 0 ~ 99까지 순회하며 4개의 좌표가 모두 true라면 정사각형 가능 
                    result++;
            }
        }
        return result;
    }
    
    static class Start {
        int x; // x 좌표 
        int y; // y 좌표 
        int dir; // 방향성 
        int g; // 세대 
        
        Start (int x, int y, int dir, int g) {
            this.x = x;
            this.y = y;
            this.dir = dir; 
            this.g = g;
        }
    } 
    
    static class Point {
        int x;
        int y;
        
        Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

2. 풀이 중점 사항

참조#1

특정 좌표를 기준으로 90도 시계방향 회전은 행렬의 회전을 이용할 수 있습니다.

이전에 AI 공부할 때, 행렬 회전 공식을 암기했던 적이 있는데, 이번에 쓰이게 되어서 요긴하게 잘 쓸 수 있었던 것 같습니다.

예를 들어 (4, 2)가 회전해야 하는 점이고, 기준점이 (4, 1)이라면 다음의 공식으로 구할 수 있습니다.

• sin90은, 1, 코사인90은 0입니다.
• Xnew = 0 * (4 - 4) + -1 * (2 - 1) = -1, Ynew = 1 * (4 - 4)  + 0 * (2 - 1) = 0 인 2 by 1 행렬을 구할 수 있습니다.
• x' = -1 + 4 = 3, y' = 0 + 1 = 1     
• 행렬 계산으로 인해 두 행렬을 계산하면 (3, 1)을 구할 수 있습니다.

따라서 이를 일반화 처리하면 

int nextX = -(y - refer.y) + refer.x;
int nextY = (x - refer.x) + refer.y;

--------------------------

int nextX = refer.x + (refer.y - y);
int nextX = refer.y - (refer.x - x);

로 공식을 구할 수 있습니다.

참조#2

만약 처리해야하는 값이 리스트에

0, 1가 있습니다.

1은 참조점이므로 0만 회전하여 나온 값이 2라면,

0 -> 2 로 리스트에 담기게 됩니다.

현재 리스트: 0, 1, 2 

참조점 2를 제외하고 내림차순으로 순회를 하면,

회전을 해서 나온 결과가

1  -> 3,

0  -> 4라고 하겠습니다,

현재 리스트: 0, 1, 2, 3, 4

참조점 4를 제외하고 다시 회전을 진행하면 0, 1, 2, 3, 4, 5, 6, 7, 8

즉, 최종적으로 가장 마지막에 끝나는 인덱스는 처음 리스트 0에 의해 회전한 값이 설정되게 됩니다.

따라서, 내림차순으로 순회하되, 하나씩 리스트에 추가하고 항상 마지막에 추가된 값을 다시 참조점으로 설정할 수 있습니다.

Point refer = nowPoints.get(nowPoints.size() - 1); // 마지막 입력은 모두 참조점이 됨 
int prePointIdx = nowPoints.size() - 2; // 참조점을 제외하고 회전시킬 인덱스 (계속 리스트에 추가하므로 인트값을 설정 해야 함)
for (int i = prePointIdx; i >= 0; i--) { // 내림차순 인덱스로 설정 참조 #2 
    Point p = nowPoints.get(i);
    int nextX = refer.x + (refer.y - p.y); // 공식 적용 
    int nextY = refer.y - (refer.x - p.x);
    map[nextX][nextY] = true;
    nowPoints.add(new Point(nextX, nextY)); // 다음 좌표 리스트에 추가 
}

따라서, 참조점을 설정한 후, 참조점보다 하나 적은 인덱스부터 내림차순 하여 회전한 값을 다시 리스트에 넣는 방법을 적용할 수 있습니다.

재귀로 인해 세대보다 하나가 커질 때까지 계속 드래곤 커브를 생성할 수 있습니다.

이상으로 드래곤 커브 자바 풀이를 마치도록 하겠습니다.

감사합니다.!!

회전 행렬 자료 출처: https://gaussian37.github.io/math-la-rotation_matrix/

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 사다리 조작 문제를 해결하는 과정을 작성하고자 합니다.

사다리 조작 문제는 해결법을 찾지 못하여 다른 블로그 분의 코드를 참조하였습니다.

문제 출처: https://www.acmicpc.net/problem/15684

1. 풀이 소스:

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        int h = parseInt(st.nextToken());

        Ladder ladder = new Ladder(n, h);
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            ladder.setMap(parseInt(st.nextToken()), parseInt(st.nextToken()));
        }

        ladder.start();
        System.out.println(ladder.getMinAddEdge());
    }
}

class Ladder {
    int n; // 열 개수
    int h; // 행 개수
    int[][] map;
    int minAddEdgeCnt = 4; // 최소 추가 설치 사다리 개수 (만약 4가 바뀌지 않는다면 -1)

    Ladder (int n, int h) {
        this.n = n;
        this.h = h;
        map = new int[h + 2][n + 2]; // (1, 1)  ~ (h ~ )이므로 h + 2
    }

    void setMap(int row, int col) {
        map[row][col] = 1;
    }

    void start() {
        for (int i = 0; i <= 3; i++) dfs(0, i, 1); // dfs로 추가 사다리가 0인 것부터 0 ~ 3까지 탐색
    }

    void dfs(int cnt, int limit, int r) {
        if (cnt > limit || cnt > minAddEdgeCnt) return; // 만약 추가한 사다리가 한계치 (0 ~ 3)으로 설정한 값보다 크거나 최대치를 넘는다면 종료

        if (isPossible()) {
            minAddEdgeCnt = Math.min(minAddEdgeCnt, cnt);
            return;
        }

        for (int row = r; row <= h; row++) { // 각 몇번째 행에서부터
            for (int col = 1; col <= n; col++) { // 1번열 (1, 1) ~ n개까지 (총 n개의 열)
                if (map[row][col] == 0 && map[row][col - 1] == 0 && map[row][col + 1] == 0) { // 참조 #1
                    map[row][col] = 1; //  현재 열 선택 가능
                    dfs(cnt + 1, limit, row); // 사다리를 하나 추가하여 이어서 dfs 진행
                    map[row][col] = 0; // dfs 종료 후 다시 이전에 설정한 1을 초기화
                }
            }
        }
    }

    boolean isPossible() {
        for (int col = 1; col <= n; col++) {
            int nowC = col; // 현재 선택한 열 번호
            int row = 1; // 행의 시작은 1
            while (true) {
                if (row > h) break; // 만약 h의 길이보다 크다면
                if (map[row][nowC] == 1) nowC++; // 1이라면 오른쪽으로 연결
                else if (map[row][nowC - 1] == 1) nowC--;// 이전항이 1이라면 이전항에서 연결한 것임
                row++; // 한번 이동했다면 그 열에서는 연속적으로 다음 열로 이동할 수 없기에 바로 내려갈 수 있음
            }

            if (nowC != col) return false; // 만약 열을 이동하고 최종적으로 마지막 행을 지나 도착했을 때, 이전 열과 다르다면
        }
        return true;
    }


    int getMinAddEdge() {
        return minAddEdgeCnt == 4 ? -1 : minAddEdgeCnt;
    }
}

2. 풀이 중점 사항

참조#1

이 문제는 사다리를 조작할 때, 0 ~ 3가지의 사다리를 어떻게 놓을 것인가가 관건이었습니다. 같은 행의 하나의 열 B는 인접한 A와 C열에 동시에 사다리가 놓일 수 없습니다. 

즉    A      B      C

        |  ---  |  --- | 

이러한 식으로, 사다리를 놓을 수 없습니다. 

if (map[row][col] == 0 && map[row][col - 1] == 0 && map[row][col + 1] == 0) { // 참조 #1

이 소스가 의미하는 바는 만약 col이 B라고 가정하면, B보다 열 인덱스가 하나 작은 A열과 인덱스가 하나 큰 C 열의 값이 모두 0일 때만 map[row][col] = 1로 사다리를 놓을 수 있습니다.

map[row][col] = 1 이 의미하는 바는, col 열과 인접한 col + 1번 열에 사다리를 놓겠다는 의미입니다.

if map[row][col - 1] == 1이라면 col - 1와  인접한 인덱스가 하나 큰 col에 사다리를 놓았다는 것을 의미하므로

같은 행에 하나의 열은 두 개의 사다리를 놓을 수 없다라는 원칙에 위배되게 됩니다.

반대로 만약

if map[row][col + 1] == 1 이라면, 이 것은 col + 1 열과 인접한 col + 2에 사다리를 놓겠다는 것을 의미합니다. 만약 map[row][col] 이 사다리를 놓게 된다면 col + 1은 이 사다리를 공유하게 되는데, 이미 col + 1과 col + 2가 사다리를 하나 공유하고 있으므로
이 또한, 같은 행에 하나의 열은 두 개의 사다리를 놓을 수 없다는 원칙에 위배되게 됩니다.

따라서, 자신의 열과 인접한 두 열을 함께 비교해야 합니다.

(그러므로 h + 2 개로 초기화 map을 설정한 것과 일맥 상통합니다)

참조 #2

boolean isPossible() { // 참조#2
    for (int col = 1; col <= n; col++) {
        int nowC = col; // 현재 선택한 열 번호
        int row = 1; // 행의 시작은 1
        while (true) {
            if (row > h) break; // 만약 h의 길이보다 크다면
            if (map[row][nowC] == 1) nowC++; // 1이라면 오른쪽으로 연결
            else if (map[row][nowC - 1] == 1) nowC--;// 이전항이 1이라면 이전항에서 연결한 것임
            row++; // 한번 이동했다면 그 열에서는 연속적으로 다음 열로 이동할 수 없기에 바로 내려갈 수 있음
        }

        if (nowC != col) return false; // 만약 열을 이동하고 최종적으로 마지막 행을 지나 도착했을 때, 이전 열과 다르다면
    }
    return true;
}

이 코드와 비교하여 제가 이전에 실수했던 부분은, row++를 else에 넣었다는 점입니다.

문제는 nowC는 컬럼의 이동을 의미하는데, 같은 행의 열은 두 개의 사다리를 가질 수 없습니다.

즉 한 번 좌 혹은 우로 이동했다면 혹은 하지 않았다면 이는 곧바로 행을 한 칸 내려가야 한다는 것을 의미합니다.

즉      A      B      C

 1       |  ---  |       | 

 2       |       |        |

 3       |       |        |

만약 1행 B에서 출발하였다면 A와 사다리가 연결되어 있어서 A 열로 이동하고 1행 1열에서 2행 1열로 내려야 하는 것입니다.

만약 내리지 않는다면, 무한 루프에 빠지게 됩니다.

자세한 코드는 주석으로 처리하였습니다.

이상으로 백준 SW 기출문제 사다리 조작 문제 풀이를 마치도록 하겠습니다.

감사합니다.!!!

참고 자료: https://suhyeokeee.tistory.com/119