구름톤 챌린지: 4주차(230906~230908)

230906

Day18 문제풀이

코드

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

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

        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(tk.nextToken());
        int M = Integer.parseInt(tk.nextToken());

        long[][][] board = new long[N][N][2]; // 보드Y 보드X 가로세로

        for(int i=0; i<M; i++) {
            tk = new StringTokenizer(br.readLine(), " ");
            int y = Integer.parseInt(tk.nextToken()) - 1;
            int x = Integer.parseInt(tk.nextToken()) - 1;
            String direction = tk.nextToken();

            switch(direction) {
                case "U" :
                    for(int a=y; a>=0; a--) board[a][x][1]++;
                    break;
                case "D" :
                    for(int a=y; a<N; a++) board[a][x][1]++;
                    break;
                case "L" :
                    for(int a=x; a>=0; a--) board[y][a][0]++;
                    break;
                case "R" :
                    for(int a=x; a<N; a++) board[y][a][0]++;
            }
        }

        long count = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                count += (board[i][j][0] * board[i][j][1]);
            }
        }
        System.out.print(count);
    }
}

중요

• 마지막 테스트케이스만 자꾸 실패하였는데 board와 count의 자료형을 int에서 long으로 바꿈으로써 성공하였다.
  오버플로우에 주의하자.

230907

Day19 문제풀이

코드

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

class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int N, S, E;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(tk.nextToken()); // 도시의 수
        int M = Integer.parseInt(tk.nextToken()); // 도로의 수
        S = Integer.parseInt(tk.nextToken()) - 1; // 출발 도시
        E = Integer.parseInt(tk.nextToken()) - 1; // 도착 도시

        for(int i=0; i<N; i++) graph.add(new ArrayList<Integer>());

        for(int i=0; i<M; i++) {
            tk = new StringTokenizer(br.readLine(), " ");

            int u = Integer.parseInt(tk.nextToken()) - 1;
            int v = Integer.parseInt(tk.nextToken()) - 1;

            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        for(int i=0; i<N; i++) System.out.println(bfs(i));
    }

    public static int bfs(int R) {
        // 시작 도시나 도착 도시가 공사중일 경우 -1 반환
        if(S == R || E == R) return -1;

        int[] visited = new int[N];
        visited[S] = 1;

        Queue<Integer> queue = new LinkedList();
        queue.offer(S);

        while(!queue.isEmpty()) {
            int u = queue.poll();

            for(int v : graph.get(u)) {
                // 공사중일 경우 지나갈 수 없음
                if(v == R) continue;

                if(visited[v] == 0 || (visited[v] != 0 && visited[v] > visited[u] + 1)) {
                    visited[v] = visited[u] + 1;
                    queue.offer(v);
                }
            }
        }

        if(visited[E] == 0) return -1;
        else return visited[E];
    }
}

중요

• 시작도시에서 도착도시로 가는 최단 거리를 찾아야 하기 때문에, 이미 방문했더라도 기존의 거리보다 가까울 경우 재방문하는 경우도 체크해주어야 한다. ( visited[v] != 0 && visited[v] > visited[u] + 1) )

230908

Day20 문제풀이

코드

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

class Main {
    static class Node {
        int y;
        int x;

        Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static int N, K;
    static String[] board;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(tk.nextToken());
        K = Integer.parseInt(tk.nextToken());
        int Q = Integer.parseInt(tk.nextToken());

        board = new String[N*N];
        for(int i=0; i<N; i++) {
            String[] split = br.readLine().split("");
            for(int j=0; j<N; j++) {
                board[i*N + j] = split[j];
            }
        }

        for(int i=0; i<Q; i++) {
            tk = new StringTokenizer(br.readLine(), " ");
            int y = Integer.parseInt(tk.nextToken()) - 1;
            int x = Integer.parseInt(tk.nextToken()) - 1;
            String d = tk.nextToken();

            board[y*N+ x] = d;

            bfs(y, x);
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                sb.append(board[i*N + j]);
            }
            sb.append("\n");
        }

        bw.write(sb.toString());

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

    public static void bfs(int y, int x) {
        int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        boolean[] visited = new boolean[N*N];
        String[] origBoard = board.clone();

        int count = 1;
        Queue<Node> queue = new LinkedList();
        queue.offer(new Node(y, x));
        board[y*N + x] = ".";
        visited[y*N + x] = true;

        while(!queue.isEmpty()) {
            Node u = queue.poll();

            for(int i=0; i<direction.length; i++) {
                int Y = u.y + direction[i][0];
                int X = u.x + direction[i][1];
                if(Y < 0 || Y >= N || X < 0 || X >= N) continue;
                if(visited[Y*N + X]) continue;

                if(origBoard[Y*N + X].equals(origBoard[u.y*N + u.x])) {
                    board[Y*N + X] = ".";
                    visited[Y*N + X] = true;
                    queue.offer(new Node(Y, X));
                    count++;
                }
            }
        }

        if(count < K) board = origBoard;
    }
}

중요

• 한 번 접근한 인덱스에 방문 처리를 해주지 않아 시간초과의 늪에 빠졌었다. 방문 처리를 해주지 않으면 시간적인 면에서 굉장히 불리하니 절대 잊지 않도록 해야 한다.
• StringBuilder를 사용하면 속도와 메모리 측면 모두 효율적으로 문자열을 만들 수 있다.