구름톤 챌린지 3주 차 학습 일기 (Day11 ~ 13)

🧩 문제 11. 통증 (2)

---

> 배운 점

• 그리디 알고리즘의 반례를 생각해봤을 때 안 됨 ➡ DP 문제

• 이전에 구했던 답 재활용하는 방식 = 메모이제이션

 

- 최소 개수 찾는 문제 ➡ 큰 수로 초기화
- 최대 개수 찾는 문제 ➡ 작은 수로 초기화

 

 

> 느낀 점

: dp는 역시.... 점화식 찾기가 쉽지 않은 것 같다....ㅋㅋㅋㅋㅠ

 

DP[ i ] : 통증 수치가 i일 때, 통증 수치를 0으로 만들기 위해 필요한 아이템의 최소 개수

- i - A >= 0 이고 MAX_VALUE가 아닌 경우, DP[i] = DP[i - A] + 1

- i - B >= 0 이고 MAX_VALUE가 아닌 경우, DP[i] = DP[i - B] + 1

 

 

> 헷갈렸던 점

: 점화식을 찾는 과정이 헷갈렸다.....

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        ..code
        dp[0] = 0;
 
        for (int i = 0; i <= N; i++) {
 
            if (i - A >= 0 && dp[i - A] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - A] + 1);
            }
 
            if (i - B >= 0 && dp[i - B] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - B] + 1);
            }
        }
 
    }
}

 

 

 

 

🧩 문제 12. 발전기

---

> 배운 점

행렬에서의 효율적 탐색

 

 

> 느낀 점

: BFS를 활용해 풀었는데 재밌었다.

문제를 제대로 읽지 않아 좀 헤맸는데

다음부터는 문제 풀이 시간을 줄이기 위해서 꼭 문제를 제대로 읽어야겠다고 생각했다.

 

> 헷갈렸던 점

: 처음에 문제를 제대로 안 읽어서 값이 0인 칸을 1로 채워야 하는 줄 알고 그 방향으로 문제를 풀었다.

근데 그게 아니었다.

방문하지 않았고 (=발전기가 없고) 값이 1인 칸 만 고려해서 bfs 수행하고, 그 bfs 수행 횟수를 구하면 되는 것이었다...

 

for(int i = 0 ; i < N ; i++) {
    for(int j = 0 ; j < N ; j++) {
 
        if(!visited[i][j] && map[i][j] == 1) {
            bfs(i, j);
            cnt++;
        }
 
    }
}

 

 

 

🧩 문제 13. 발전기(2)

---

> 배운 점

행렬에서의 효율적 탐색 + 완전 탐색

(현대 ㅁㅂㅅ 알고리즘 대회 변형 문제?!)

 

 

> 느낀 점

: 방문하지 않은 점에서 bfs를 수행하고,

연결된 건물 갯수가 K개 이상일 때 단지 갯수를 업데이트하고,

전력을 공급할 건물 유형을 구하도록 했다.

 

나는 Map에 단지 번호와 단지 개수를 저장해두고 사용했는데,

정답 코드 보니까 🟠 배열을 만들어 단지 개수를 저장🟠했다.

(score[target]++ 이런 식으로!)

 

그리고 전력 공급도... 쉽게 하심!

반복문을 31~0까지 역순으로 돌려서

score[i] > score[maxIdx]면 maxIdx = i로 설정하는 식으로!!

 

(정답 풀이 링크 : https://goorm.notion.site/2-Java-c21296fe74ad40cb873867b7f7e6c24f)

 

 

> 헷갈렸던 점

: 가장 많은 단지를 갖고 있는 건물이 여러 개인 경우,

건물 번호가 가장 큰 건물을 정답으로 출력하면 되는데,

문제를 꼼꼼히 안 읽어서 (x,y)좌표가 가장 뒤쪽인 건물을 출력하라는 건 줄 알고 좀 헤맸다.

 

 

정답 코드 확인하기

import java.io.*;
import java.util.*;
 
class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int N, K, answer;
    static int[][] map;
    static boolean[][] visited;
    
    static int max = Integer.MIN_VALUE;
    
    static Map<Integer, Integer> hm = new HashMap<>();  // Map<단지 번호, 단지 개수>
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        map = new int[N][N];
        visited = new boolean[N][N];
        
        // 입력 받기
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(!visited[i][j]) {
                    int val = bfs(i, j);
                    
                    // "단지" : 전력 공유 가능 관계인 건물 수가 K개 이상이어야 함
                    if(val < K) continue; 
                    
                    // 단지라면, 단지 개수 업데이트 & 전력 공급
                    hm.put(map[i][j], hm.getOrDefault(map[i][j], 0) + 1);
                    electrify(i, j);
                }
            }
        }
        
        System.out.println(answer);
    }
    
    // [전력 공유 가능 관계인 건물 수 구하는 메소드]
    private static int bfs(int a, int b) {
        int cnt = 1;
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a, b});
        
        visited[a][b]  = true;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int x = now[0] + dx[d];
                int y = now[1] + dy[d];
                
                if(x < 0 || y < 0 || x >= N || y >= N || visited[x][y] || map[x][y] != map[a][b])    continue;
                if(!visited[x][y] && (map[x][y] == map[a][b])) {
                    visited[x][y] = true;
                    cnt += 1;
                    queue.add(new int[] {x, y});
                }
            }
        }
        
        return cnt;
    }
    
    // [전력 공급 메소드]
    private static void electrify(int i, int j) {            
        // 가장 많은 단지가 있는 건물 유형에 전력 공급
        if(hm.get(map[i][j]) > max) {
            max = hm.get(map[i][j]);
            answer = map[i][j];
        }
        // 가장 많은 단지가 있는 건물 유형이 여러 개인 경우, 번호가 더 큰 건물 유형에 전력 공급
        else if(hm.get(map[i][j]) == max) {
            answer = Math.max(answer, map[i][j]);
        }   
    }
}

 

---

그리디 문제 말고는 BFS 문제여서 재밌게 풀었다!