구름톤 챌린지 5주 차 학습 일기 (Day19 ~ 20)

🧩 문제 19. 대체 경로

---

힙쟁이~~

> 배운 점

•  그래프 탐색 - BFS / DFS

(최단 경로니까 BFS 활용)

- 최단 경로 찾는 문제 ➡ 방문 배열을 int형 배열로 받고, 큰 수로 초기화

 

 

> 느낀 점

방문 배열 visited를 처음에 boolean으로 했었는데, 이러면 결과 배열 int[] result를 따로 만들어야 하고 그렇다...

 

그래서 방문 배열 visited를 int형으로 만들고, 이걸 최단 거리 저장 배열로 만들고, 배열의 초기값은 큰 값으로 설정하는 것이다.

 

그리고 bfs에 왜 idx 값을 가져가야 하냐면, "i일 뒤 i번 도시로 이동하면 안 된다"는 조건을 만족시키기 위해

몇 번 도시인지 도시 위치 값을 기억하기 위해서다.

 

만약 A(현재 위치로 가는 최단 경로 값 + 1)  <  B(다음 위치로 가는 최단 경로)라면,

B를 A로 갱신해준다.

만약 다음 위치가 도착 도시라면, BFS문을 종료한다.

 

 

> 헷갈렸던 점

• "i일에는 i번 도시를 경유할 수 없다"는 조건을 빠뜨렸다,,,,

 

• 최소 경로 찾는 문제니까, 배열을 큰 수로 초기화하는 과정이 필요한데 이 과정도 놓쳤었다.ㅋㅋㅋ🤦‍♀️🤦‍♀️

(그래서 약간 다익스트라 문제인가....하는 생각도 했었다)

 

• 더 작은 값으로 갱신하는 과정도 놓쳤었다,,,,,, 

 

• 방문 배열을 int형 배열로 받아, 최단 거리를 저장하는 배열을 만든다!

  그러면 방문 처리와 방문한 도시 개수를 저장하는 역할을 동시에 수행할 수 있다. 🤗

 

• 약간 다익스트라 문제인가..?생각했는데 가중치가 없으니 BFS 문제였다.

 

정답 코드 확인하기

import java.io.*;
import java.util.*;
 
class Main {
    static int N, M, S, E;
    
    static ArrayList<Integer>[] A;
    static int[] visited;    // 🔔 최단 거리 저장 배열
    
    static StringBuilder sb = new StringBuilder();
    
    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()); // 도시 수
        M = Integer.parseInt(st.nextToken()); // 도로 수
        S = Integer.parseInt(st.nextToken()); // 출발 도시
        E = Integer.parseInt(st.nextToken()); // 도착 도시
        
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
                
        // 입력 받기 (양방향)
        for(int i = 1 ; i <= M ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            A[u].add(v);
            A[v].add(u);
        }
        
        for(int i = 1 ; i <= N ; i++) {
            if (i == S || i == E) sb.append(-1).append("\n");
            else {
                visited = new int[N + 1];    // visited 배열은 매번 새롭게 선언
                Arrays.fill(visited, Integer.MAX_VALUE);    // 🔔 최단 거리 저장 배열, 초기값은 최대한 큰 수로 저장
 
                int tmp = bfs(S, i);
                sb.append(tmp).append("\n");
            }
        }
                          
        System.out.println(sb);
    }
    
    private static int bfs(int num, int idx) {
        Queue<Integer> q = new LinkedList<>();
        q.add(num);
        
        visited[num] = 1;    // 방문 처리
        
        while (!q.isEmpty()) {
            int now = q.poll();
            
            for (int next : A[now]) {
                if (next != idx) {    // 🔔 i일 뒤, i번 도시로 이동하면 안 됨.
                    if(visited[next] > visited[now] + 1) {    // 더 작은 값으로 갱신
                        visited[next] = visited[now] + 1;
                        q.add(next);
                    }
                    
                    if(next == E) break;    // 도착 도시에 도착하면, 종료
                }
            }
        }
        
        return (visited[E] == Integer.MAX_VALUE) ? -1 : visited[E];
    }
}
 

 

 

 

🧩 문제 20. 연결 요소 제거하기

---

> 배운 점

•  시뮬레이션 + 그래프 탐색 (BFS / DFS)

 

 

> 느낀 점

• 필요한 자료구조가 무엇인지 초장에 잘 생각하고 넘어가자..

이번에는 연결 요소 리스트를 놓침

 

[진행 순서]

1. 입력 받기

2. BFS 수행하며 상하좌우 인접한 연결고리를 생성하며, 모든 연결 가능한 요소를 리스트에 저장한다.

3. 연결 요소 리스트의 크기가 K 이상이면, 해당 연결 요소에 포함된 모든 칸에 적힌 문자를 '.'으로 바꾼다.

 

• 시뮬레이션 문제를 더 풀어봐야겠다,,, 

 

 

> 헷갈렸던 점

•  연결 고리에 속한 연결 요소 정보 저장 리스트를 만들 생각을 하지 못 했다...

List<Pos> list = new ArrayList<>();

 

 

• y와 x가 바뀌면 조굼 헷갈린다,,

 

 

(참고)

https://tussle.tistory.com/1079

정답 코드 확인하기

import java.io.*;
import java.util.*;
 
class Pos {
    int y, x;
    
    public Pos(int y, int x) {
        this.y = y;
        this.x = x;
    }
}
 
class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int N,K,Q;
    static char[][] arr;
    static boolean[][] visited;
    
    static StringBuilder sb = new StringBuilder();
    
    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());
        Q = Integer.parseInt(st.nextToken());
        
        arr = new char[N][N];
        visited = new boolean[N][N];
        
        // 배열 정보 저장    
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            Arrays.fill(arr[i], '.');
            
            for(int j = 0 ; j < N ; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        
        for(int i = 0 ; i < Q ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int y = Integer.parseInt(st.nextToken()) - 1;
            int x = Integer.parseInt(st.nextToken()) - 1;
 
            char c = st.nextToken().charAt(0);
            arr[y][x] = c;
 
            bfs(y, x, c);    // 연결 요소 구하기
        }
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++)
                sb.append(arr[i][j]);
            sb.append("\n");
        }
        
        System.out.println(sb);
    }
    
    // 🔔 BFS 통해 상하좌우 연결고리 만드는 함수 🔔
    private static void bfs(int y, int x, int c) {
        Queue<Pos> queue = new LinkedList<>();
        queue.offer(new Pos(y, x));
        
        // 📍 연결 고리에 속한 연결 요소 정보 저장 리스트
        List<Pos> list = new ArrayList<>();    
        list.add(new Pos(y, x));
        
        visited = new boolean[N][N];
        visited[y][x] = true;
        
        while(!queue.isEmpty()) {
            Pos now = queue.poll();
 
            for(int d = 0 ; d < 4 ; d++) {
                int ny = now.y + dy[d];
                int nx = now.x + dx[d];
 
                if(nx < 0 || ny < 0 || nx >= N || ny >= N)    continue;
 
                if(!visited[ny][nx] && arr[ny][nx] == c) {
                    visited[ny][nx] = true;
                    list.add(new Pos(ny, nx));  // 📍 연결고리에 속한 연결 요소, List에 저장
                    queue.add(new Pos(ny, nx));
                }
            }            
        }
        
        // 연결요소 >= K가 성립할 때, 해당 칸을 모두 '.'으로 변경하기
        if(list.size() >= K) {
            for(Pos now : list) {
                arr[now.y][now.x] = '.';
            }
        }
    }
}