GOSE_KOSE

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

이번 포스팅은 백준 DP문제 - 동전 2 자바 풀이를 진행하고자 합니다.

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

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 k = parseInt(st.nextToken());
        Coin coin = new Coin(n, k);
        
        for (int i = 0; i < n; i++) {
            coin.setCoin(parseInt(br.readLine()));
        }
        
        coin.run();
        System.out.println(coin.getResult());
    }
}

class Coin {
    int n;
    int k;
    int[] dp; // 각 인덱스에 들어갈 값은 코인의 최소 개수
    int result; // 결과 저장 
    List<Integer> coins = new ArrayList<>(); // 코인 값 저장 
    
    Coin (int n, int k) {
        this.n = n;
        this.k = k;
        dp = new int[k + 1]; 
        Arrays.fill(dp, Integer.MAX_VALUE); // 모두 최고값으로 초기화
    }
    
    void setCoin(int won) {
        coins.add(won);
    }
    
    void run() {
        
        dp[0] = 0; // 0을 만드는 경우는 0개임
        for (int i = 1; i <= k; i++) {
            for (Integer coin : coins) {
                if (i - coin < 0 || dp[i - coin] == Integer.MAX_VALUE) continue; // 만약 인덱스가 0 미만이거나, 만들 수 없는 값인 경우
                dp[i] = Math.min(dp[i - coin] + 1, dp[i]); // 코인의 값을 인덱스로 뺀다면 그 값이 설정   
            }
        }
        
        if (dp[k] == Integer.MAX_VALUE) result = -1;
        else result = dp[k];
    }
    
    int getResult() {
        return result;
    }
    
}

2. 풀이 중점 사항

Memozation을 사용할 DP를 금액으로 설정하고 문제를 해결하였습니다.

각 동전은 coin이라는 리스트에 저장한 후,

1 ~ k까지 (각 경계 포함) for문을 돌리되, 각 코인을 내부에서 순환합니다. (빅오 n^2)

dp[i] = Math.min(dp[i - coin] + 1, dp[i]); // 코인의 값을 인덱스로 뺀다면 그 값이 설정

dp[i - coin]은 dp는 금액을 메모한 배열이므로 i - coin은 i - coin 금액에 있는 동전 최소 개수가 됩니다.

즉, 동전이 500이고, 현재 i = 700일 때, dp[200]에서 500원 동전 한 개만 더해주면 700을 만들 수 있는 원리입니다.

따라서 다음의 점화식을 작성하여 문제를 해결할 수 있었습니다.

이상으로 DP 동전 2 문제 풀이를 마치도록 하겠습니다. 감사합니다.!!

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

이번 포스팅은 백준 DP 문제 모음 스티커 자바 풀이를 진행하고자 합니다.

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

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));
        int t = parseInt(br.readLine());

        Sticker sticker = new Sticker();
        for (int i = 0; i < t; i++) {
            int n = parseInt(br.readLine());
            sticker.setInit(n);
            for (int row = 0; row < 2; row++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int col = 1 ; col <= n; col++)
                    sticker.setMap(row, col, parseInt(st.nextToken()));
            }
            sticker.run();
        }

        sticker.printResult();

    }    
}

class Sticker {
    int n;
    int[][] dp;
    int[][] map;
    List<Integer> result = new ArrayList<>();
    
    Sticker () {
    }

    void setInit(int n) {
        this.n = n;
        dp = new int[2][n + 1]; // dp를 담을 2차원 배열 
        map = new int[2][n + 1]; // 각 스티커의 값
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value; 
    }
    
    void run() {
        dp[0][1] = map[0][1]; // i가 2부터이므로 1을 초기화 
        dp[1][1] = map[1][1];
        
        for (int i = 2; i <= n; i++) {
            dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + map[0][i];
            dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + map[1][i];
        }
        result.add(Math.max(dp[0][n], dp[1][n]));
    }

    void printResult() {
        StringBuilder sb = new StringBuilder();

        for (Integer r : result) {
            sb.append(r).append("\n");
        }
        System.out.print(sb);
    }
}

2. 풀이 중점 사항

평소 DP가 약하여, 점화식을 도출하는 것에서 바로 떠오르지 않아 이러한 형태의 문제에서는 자동적으로 

현재 DP = Math.max(이전 DP, 이전*2 DP)를 적어놓고 문제를 다시 보곤 합니다.

이 문제에서 중점 사항은 면이 인접하지 않게 골라야 하므로, 현재 선택지에서 최댓값은 이전 인덱스의 DP의 최댓값이면서, 행이 다른 DP, 그리고 인덱스가 2개 적은 DP의 다른 행 DP의 최댓값을 비교한 후, 더 큰 것에 현재의 값을 구하는 방식입니다.

for (int i = 2; i <= n; i++) {
    dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + map[0][i];
    dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + map[1][i];
}
result.add(Math.max(dp[0][n], dp[1][n]));

이러한 코드가 가능한 이유는, 다음과 같습니다.

60 70 100 20

70 700 10 900 이 있다고 가정하겠습니다.

20의 입장에서 최대를 선택하는 것은 각 열에 인접하지 않게 선택하여 값을 늘리는 것입니다.

70 70 10 이 될 수 있고, 60 700 이 될 수 있습니다.

(60 700 100 은 20에 100이 인접하므로 될 수 없습니다. || 70 70은 10을  추가로 선택할 수 없으므로 최대값이 되지 못합니다.)

따라서, 점화식은 위의 코드와 같이 구성될 수 있습니다.

2차원 배열이므로, 위 아래 각각 DP를 적용하고, 최종적으로 마지막 인덱스에서 두 DP 중 더 큰 값을 선택하여 값을 도출할 수 있습니다.

이상으로 스티커 자바 풀이를 마치도록 하겠습니다. 감사합니다.!!

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

이번 포스팅은 백준 SW 기출문제 원판 돌리기 자바 풀이를 작성하도록 하겠습니다.

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

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 t = parseInt(st.nextToken());
        
        Board board = new Board(n, m);
        
        for (int row = 1; row <= n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= m; col++) {
                board.setMap(row, col, parseInt(st.nextToken()));
            }
        }
        
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int x = parseInt(st.nextToken()); // 배수 행
            int dir = parseInt(st.nextToken()); // 방향
            int k = parseInt(st.nextToken()); // 칸 수
            board.rotate(x, dir, k);
        }
        
        System.out.println(board.getSum());
    }
}

class Board {
    int n; // 행의 개수
    int m; // 열의 개수
    int[][] map;
    int[] tmp; // 임시 swap 배열
    
    Board(int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n + 1][m + 1];
        tmp = new int[m + 1];
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }
    
    // dir -> 시계: 0, 반시계: 1
    void rotate(int x, int dir, int k) { // x는 row 배수 형태로
        for (int row = 1; row <= n; row++) {
            if (row % x == 0) { // x의 배수
                swap(map[row], k, dir);
            }
        }

        int leftCol; // 인접한 왼쪽 열
        int rightCol; // 인접한 오른쪽 열
        
        int totalSum = 0; // 총 합
        int totalCnt = 0; // 총 개수
        List<Point> zeros = new ArrayList<>(); // zero가 되는 포인트
        
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= m; col++) {
                int flag = zeros.size(); // zeros.size가 변한다면 인접한 것이 있다는 의미
                int nowValue = map[row][col];

                if (nowValue == 0) continue; // 만약 현재 값이 0인 것은 건너뛰기

                totalSum += nowValue;
                totalCnt++;
                
                if (col == 1) { // 맨 좌측 열은 맨 우측 열 인접하도록 설정하기
                    leftCol = m;
                    rightCol = col + 1; 
                } else if (col == m) {
                    leftCol = m - 1;
                    rightCol = 1;
                } else { // 나머지는 양쪽 열
                    leftCol = col - 1;
                    rightCol = col + 1;
                } 
                
                if (map[row][leftCol] == nowValue) {
                    zeros.add(new Point(row, leftCol));
                }
                
                if (map[row][rightCol] == nowValue) {
                    zeros.add(new Point(row, rightCol));
                }
                
                if (row == 1) { // 맨 윗행은 인접한 행이 바로 아래 행
                    if (nowValue == map[row + 1][col]) zeros.add(new Point(row + 1, col));
                } 
                else if (row == n) { // 맨 아래 행의 인접한 행은 바로 윗행
                    if (nowValue == map[row - 1][col]) zeros.add(new Point(row - 1, col));
                } 
                else {
                    if (nowValue == map[row + 1][col]) zeros.add(new Point(row + 1, col));
                    if (nowValue == map[row - 1][col]) zeros.add(new Point(row - 1, col));
                }

                if (zeros.size() != flag) zeros.add(new Point(row, col)); // 값이 추가되었다는 것을 의미하므로 자신도 추가하기
            }

        }
        
        if (!zeros.isEmpty()) {
            for (Point p : zeros) {
                map[p.row][p.col] = 0; // 인접하여 같은 값도 zero 설정
            }
        } 
        else { // 한 번도 인접한 값이 같은 것이 없음
            if (totalCnt != 0) {
                double avg = (double) totalSum / totalCnt;
                
                for (int row = 1; row <= n; row++) {
                    for (int col = 1; col <= m; col++) {
                        int nowValue = map[row][col];
                        if (nowValue != 0 && avg < nowValue) map[row][col]--; // 평균보다 크다면 --
                        else if (nowValue != 0 && avg > nowValue) map[row][col]++; // 평균보다 작다면 ++
                    }
                }
            }
        }
    }
    
    int getSum() {
        int sum = 0;
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= m; col++) sum += map[row][col];
        }
        return sum;
    }

    // 0, 1, 2, 3, 4, 5
    // k만큼 시계 방향 회전 i + k를 하되, 인덱스를 벗어난 경우 m 빼기
    // i = 2, k = 3 => tmp[5] = 2;
    // i = 3, k = 3 => tmp[6 - 5] = 3;
    void swap(int[] arr, int k, int clockWise) { // k 만큼 스왑
        if(clockWise == 0) {    // 시계 방향 회전
            for (int i = 1; i <= m; i++) {
                int next = i + k > m ? i + k - m : i + k;
                tmp[next] = arr[i];
            }
        }

        // 반시계는 왼쪽으로 칸을 옮기되 0보다 작아질 수 있으므로 m을 더하기
        else {    // 반시계 방향 회전
            for (int i = m; i >= 1; i--) {
                int next = i - k > 0 ? i - k : i - k + m;
                tmp[next] = arr[i];
            }
        }

        System.arraycopy(tmp, 1, arr, 1, arr.length - 1);
    }
    
    static class Point {
        int row;
        int col;
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

2. 풀이 중점 사항

회전하기

가장 헷갈린 부분은 회전 처리하는 부분이었습니다.

시계 방향으로 회전을 하기 위해서는 이전 인덱스 i-1의 값이 i로 와야 하기 때문에 --> 이 방향으로 이동이 이뤄져야 합니다.

k 칸을 이동한다고 하는 것은 i번째의 값이 i + k에 도착해야 한다는 것을 의미합니다.

만약 i + k 가 m을 넘어가게 된다면 인덱스 에러가 발생합니다. 이를 해결하기 위해서는 

i + k > m ? i + k - m : i + k라는 수식을 구할 수 있습니다.

예를 들어 다음의 배열이 있습니다. (행과 열이 모두 1, 1부터 이므로 더미의 0번째 인덱스는 무시해야 합니다.)

0, 1, 2, 3, 4, 5

시계방향으로 3만큼 이동

=> 0, 4, 5, 1, 2, 3

3 인덱스는, 3 + 3으로 인해 인덱스가 6이 되어버립니다. 따라서, m만큼 개수를 빼면

6 - 5 = 1이 되어 정상적으로 위치 회전을 할 수 있습니다.

반시계 방향은 <-- 으로 이동해야 합니다.

수식은 i - k > 0? i - k : i - k + m;입니다.

0, 1, 2, 3, 4, 5 

반시계 방향으로 3만큼 이동

=> 0, 3, 4, 5, 1, 2 

1의 경우 3을 뺀다면, -2라서 에러가 발생하므로 5를 더해서 인덱스 3으로 만들 수 있습니다.

3 - 3의 경우 index가 0이지만, 0, 0은 더미로 설정하였으므로

5를 더하여 5로 설정할 수 있습니다. 4, 5는 인덱스가 0보다 크므로 i - k로 해결할 수 있습니다.

void swap(int[] arr, int k, int clockWise) { // k 만큼 스왑
    if(clockWise == 0) {    // 시계 방향 회전
        for (int i = 1; i <= m; i++) {
            int next = i + k > m ? i + k - m : i + k;
            tmp[next] = arr[i];
        }
    }

    // 반시계는 왼쪽으로 칸을 옮기되 0보다 작아질 수 있으므로 m을 더하기
    else {    // 반시계 방향 회전
        for (int i = m; i >= 1; i--) {
            int next = i - k > 0 ? i - k : i - k + m;
            tmp[next] = arr[i];
        }
    }

    System.arraycopy(tmp, 1, arr, 1, arr.length - 1);
}

점을 기준으로 특정 좌표를 회전시키거나 이렇게 swap 하는 유형은 실수하기 좋은 유형이므로 천천히 자세하게 적어가면서 해결해야 함을 느낄 수 있었습니다.

이성으로 원판 돌리기 자바 풀이를 마치겠습니다. 감사합니다.!!!

안녕하세요. 회사와 함께 성장하고 싶은 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문의 종료 조건을 만족할 수 있게 됩니다.

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