<백준> 24.07.02에 푼 문제들

1. 영역 구하기 (Silver 1)

[백준]

https://www.acmicpc.net/problem/2583

[깃허브]

ForCodeKata/baekjoon 문제집/2583 영역 구하기 at main · heesoo-park/ForCodeKata

제출 결과

---

좌표에 대한 처리를 처음에는 들어온 값을 좌측 상단 기준으로 변환하는 방법을 찾다가 머리가 너무 복잡해져서 간단한 방법을 찾다가 그냥 받아서 그대로 채우면 된다는 것을 깨닫고 진행했다.

 

값이 디버깅할 때 잘 못 나오는 경우가 있었는데 2차원 배열을 순회하는 범위를 잘못 잡은 케이스와 경계값을 잘못 설정한 케이스로 인해서 나온 것이었다.

 

LinkedList와 ArrayList를 정렬할 때는 Collections.sort를 사용하면 된다는 걸 다시 기억하게 되었다.

(물론 인자가 여러개라면 Comparator? 가 필요하지만...)

 

작성한 코드는 다음과 같다.

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

public class Main {

    static boolean[][] paper = new boolean[101][101];
    static boolean[][] visited = new boolean[101][101];
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int m, n;
    static LinkedList<Integer> ll = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int cnt = 0;

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int leftX = Integer.parseInt(st.nextToken());
            int leftY = Integer.parseInt(st.nextToken());
            int rightX = Integer.parseInt(st.nextToken());
            int rightY = Integer.parseInt(st.nextToken());

            fillPaper(leftX, leftY, rightX, rightY);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!paper[i][j] && !visited[i][j]) {
                    cnt++;
                    bfs(i, j);
                }
            }
        }

        bw.write(cnt + "\n");
        Collections.sort(ll);
        for (int num : ll) {
            bw.write(num + " ");
        }

        bw.flush();
        bw.close();
    }

    static void bfs(int sr, int sc) {
        Queue<Position> q = new LinkedList<>();
        int area = 1;
        visited[sr][sc] = true;
        q.offer(new Position(sr, sc));

        while (!q.isEmpty()) {
            Position cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dy[i];
                int nc = cur.c + dx[i];

                if (nr >= m || nr < 0 || nc >= n || nc < 0) continue;
                if (paper[nr][nc] || visited[nr][nc]) continue;

                visited[nr][nc] = true;
                area++;
                q.offer(new Position(nr, nc));
            }
        }

        ll.offer(area);
    }

    static void fillPaper(int lx, int ly, int rx, int ry) {
        for (int i = ly; i < ry; i++) {
            for (int j = lx; j < rx; j++) {
                paper[i][j] = true;
            }
        }
    }

    static class Position {
        int r;
        int c;

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

 

2. 단지번호붙이기 (Silver 1)

[백준]

https://www.acmicpc.net/problem/2667

[깃허브]

ForCodeKata/baekjoon 문제집/2667 단지번호붙이기 at main · heesoo-park/ForCodeKata

제출 결과

---

위에 풀었던 문제와 거의 유사해서 금방 해결했다.

 

작성한 코드는 다음과 같다.

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

public class Main {
    
    static char[][] map = new char[26][26];
    static boolean[][] visited = new boolean[26][26];
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int n;
    static List<Integer> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int cnt = 0;
        
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = line.charAt(j);
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == '1' && !visited[i][j]) {
                    cnt++;
                    bfs(i, j);
                }
            }
        }
        
        bw.write(cnt + "\n");
        Collections.sort(list);
        for (int num : list) {
            bw.write(num + "\n");
        }
        
        bw.flush();
        bw.close();
    }
    
    static void bfs(int sr, int sc) {
        Queue<Position> q = new LinkedList<>();
        int area = 1;
        visited[sr][sc] = true;
        q.offer(new Position(sr, sc));
        
        while (!q.isEmpty()) {
            Position cur = q.poll();
            
            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dy[i];
                int nc = cur.c + dx[i];
                
                if (nr >= n || nr < 0 || nc >= n || nc < 0) continue;
                if (map[nr][nc] == '0' || visited[nr][nc]) continue;
                
                area++;
                visited[nr][nc] = true;
                q.offer(new Position(nr, nc));
            }
        }
        
        list.add(area);
    }
    
    static class Position {
        int r;
        int c;
        
        Position(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

 

3. 스타트링크 (Silver 1)

[백준]

https://www.acmicpc.net/problem/5014

[깃허브]

ForCodeKata/baekjoon 문제집/5014 스타트링크 at main · heesoo-park/ForCodeKata

제출 결과

---

어제 풀었던 숨바꼭질 문제하고 유사한 형태의 문제여서 금방 해결할 수 있었다.

"BFS에서 특정 위치에 가장 먼저 도착한다면 그게 가장 빠른 도착이다" 라는 것을 놓치지 않았다.

 

작성한 코드는 다음과 같다.

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

public class Main {
    
    static boolean[] floor = new boolean[1000001];
    static int[] check = new int[1000001];
    static boolean isFinish = false;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int f = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        int g = Integer.parseInt(st.nextToken());
        int u = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        
        bfs(f, s, g, u, d);
        
        bw.write(isFinish ? String.valueOf(check[g]) : "use the stairs");
        bw.flush();
        bw.close();
    }
    
    static void bfs(int height, int start, int goal, int up, int down) {
        Queue<Integer> q = new LinkedList<>();
        floor[start] = true;
        q.offer(start);
        
        while (!q.isEmpty()) {
            int cur = q.poll();
            
            if (cur == goal) {
                isFinish = true;
                break;
            }
            
            int nextUp = cur + up;
            if (nextUp <= height && !floor[nextUp]) {
                floor[nextUp] = true;
                check[nextUp] = check[cur] + 1;
                q.offer(nextUp);
            }
            
            int nextDown = cur - down;
            if (nextDown > 0 && !floor[nextDown]) {
                floor[nextDown] = true;
                check[nextDown] = check[cur] + 1;
                q.offer(nextDown);
            }
        }
    }
}

 

4. 안전 영역 (Silver 1)

[백준]

https://www.acmicpc.net/problem/2468

[깃허브]

ForCodeKata/baekjoon 문제집/2468 안전 영역 at main · heesoo-park/ForCodeKata

제출 결과

---

갑자기 번뜩 생각난 방법으로 진행했는데 해결됐다.

3중 for문으로 깊이를 점점 더해가며 모든 지역을 도는 방식을 채택했다.

한번 틀렸었는데 그건 초기 상태에 대한 처리를 그냥 넘어갔기 때문에 생겼었다.

 

수 크기 비교할 때는 Math.max / Math.min을 쓰면 된다는 걸 기억했다.

코틀린은 maxOf, minOf를 주로 썼었는데...

 

작성한 코드는 다음과 같다.

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

public class Main {
    
    static int[][] region = new int[101][101];
    static boolean[][] visited = new boolean[101][101];
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int n;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int max = 0;
        
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                region[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for (int i = 0; i < 101; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (region[j][k] - i > 0 && !visited[j][k]) {
                        cnt++;
                        bfs(j, k, i);
                    }
                }
            }
            
            if (cnt == 0) break;
            
            max = Math.max(max, cnt);
            clearArray();
        }
        
        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
    }
    
    static void bfs(int sr, int sc, int depth) {
        Queue<Position> q = new LinkedList<>();
        visited[sr][sc] = true;
        q.offer(new Position(sr, sc));
        
        while (!q.isEmpty()) {
            Position cur = q.poll();
            
            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dy[i];
                int nc = cur.c + dx[i];
                
                if (nr >= n || nr < 0 || nc >= n || nc < 0) continue;
                if (region[nr][nc] - depth <= 0 || visited[nr][nc]) continue;
                
                visited[nr][nc] = true;
                q.offer(new Position(nr, nc));
            }
        }
    }
    
    static void clearArray() {
        for (boolean[] line : visited) {
            Arrays.fill(line, false);
        }
    }
    
    static class Position {
        int r, c;
        
        Position(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}