공부흔적

문제 링크

풀이 )

  처음에는 방문 여부를 나타내는 boolean 2차원 배열 visited를 선언하지 않고 풀려다가 많은 문제가 발생했다.

• 비활성화된 바이러스를 0으로 갱신하고 시작
  • 처음에 다 퍼져있는 경우에 대해서 다른 결과를 출력한다.
• 바이러스가 방문한 곳을 2로 갱신하고, 1이 아닌 곳만 방문
  
  • 큐에 중복 방문으로 인한 메모리 초과
• 바이러스가 방문한 곳을 3으로 갱신하고, 0 2인 곳만 방문
  
  • 비활성화된 바이러스를 벽으로 생각함

  결국 visited 배열을 사용해서 했다.

  자세한 풀이는 아래 주석을 달아두었다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static int n,m;
    static int[][] board;
    static int ans = (int)1e7;
    static ArrayList<Point> virusList = new ArrayList<>();

    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());
        board = new int[n][n];
        for(int i = 0; i < n; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < n; ++j){
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j] == 2){
                    virusList.add(new Point(i, j));
                }
            }
        }
        // 입력 & 비활성화된 바이러스를 list에 저장

        combination(m, new int[m], 0);	// 활성화될 바이러스 선택(조합 - virusList.size() C m)
        if(ans == (int)1e7)
            ans = -1;
        System.out.println(ans);
    }

    static void combination(int toPick, int[] picked, int pos){
        if(toPick == 0){
            bfs(picked);	// 활성화될 바이러스를 시작으로 bfs 탐색
            return;
        }

        for(int i = pos; i < virusList.size(); ++i){
            picked[picked.length-toPick] = i;
            combination(toPick-1, picked, i+1);
        }
    }

    static void bfs(int[] picked){
        int[][] tmp = new int[n][];
        for(int i = 0; i < n; ++i)
            tmp[i] = board[i].clone();	// board 값에 영향을 주지 않기 위한 임시 배열
        boolean[][] visited = new boolean[n][n];	// 방문 여부

        Queue<Point> virusQ = new LinkedList<>();
        for(int i = 0; i < picked.length; ++i){
            Point virus = virusList.get(picked[i]);
            virusQ.offer(virus);
            visited[virus.x][virus.y] = true;
        }	// 활성화될 바이러스를 큐에 집어 넣으면서 방문여부 갱신

        int time = -1;	// 바이러스가 퍼지는데 걸리는 시간
        while(!virusQ.isEmpty()){
            time++;
            boolean flag = false;	// 바이러스가 퍼졌는지 확인할 때 2중 for문을 탈출하기 위한 flag
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < n; ++j)
                    if(tmp[i][j] == 0){
                        flag = true;
                        break;
                    }
                if(flag)
                    break;
            }
            if(!flag){	// 바이러스가 더이상 퍼질 수 없으면 ans를 갱신하고 종료
                ans = Math.min(ans, time);
                return;
            }

            int size = virusQ.size();
            while(size-- > 0){
                Point cur = virusQ.poll();
                int x = cur.x, y = cur.y;
                for(int dir = 0; dir < 4; ++dir){
                    int nx = x+dx[dir], ny = y+dy[dir];
                    if(!isIn(nx, ny) || tmp[nx][ny] == 1 || visited[nx][ny])	// 확산할 수 없는 경우
                        continue;
                    visited[nx][ny] = true;	// 확산할 수 있는 경우 방문 여부와 임시 배열을 갱신하고, 큐에 추가
                    tmp[nx][ny] = 2;
                    virusQ.offer(new Point(nx, ny));
                }
            }
            if(virusQ.isEmpty())
                break;
        }
    }

    static boolean isIn(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < n;
    }
}

주의 )

  처음 ans의 값을 100으로 설정해서 틀렸다.

  초기에 주어진 바이러스가 1개이고 가로세로 50의 ㄹ모양의 연구소가 주어지면 100초 이상 걸리기 때문에 넉넉한 값을 주어야 한다.

문제 링크

풀이 )

  하나의 칸에 여러 나무가 있을 때 나이가 적은 나무부터 양분을 공급한다는 내용을 보고 우선순위큐를 사용했다.

  feed 배열에는 양분을 저장했고, a 배열에는 겨울마다 늘어나는 양분을 저장했다.

  나무의 좌표와 나이를 저장하는 우선순위큐를 만들어서 나이가 낮은 순으로 poll 되도록 구현했다.

  처음에는 우선순위큐 하나만 사용해서 구현하려고했기 때문에 큐의 크기를 먼저 구한 후 큐의 크기만큼만 반복문을 돌렸지만, 이런 경우 중간에 나이가 낮은 나무가 들어오는 경우 의도와 다르게 나오는 경우가 있었기 때문에 다른 우선순위 큐를 선언해서 사용했다.

  나머지는 문제에서 요구하는 순서대로 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] dy = {1, 1, 0, -1, -1, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] feed = new int[n+1][n+1];
        int[][] a = new int[n+1][n+1];

        PriorityQueue<Info> treeQ = new PriorityQueue<>((o1, o2)->{
            return o1.age-o2.age;
        });
        Queue<Info> dieQ = new LinkedList<>();

        for(int i = 1; i <= n; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1; j <= n; ++j){
                feed[i][j] = 5;
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < m; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int age = Integer.parseInt(st.nextToken());
            treeQ.offer(new Info(x, y, age));
        }
        // 입력

        while(k-- > 0) {
            PriorityQueue<Info> tmp = new PriorityQueue<>((o1, o2)->{
                return o1.age-o2.age;
            });
            int size = treeQ.size();
            while (size-- > 0) {
                Info tree = treeQ.poll();
                int x = tree.x, y = tree.y, age = tree.age;
                if (feed[x][y] >= age) {
                    feed[x][y] -= age;
                    age++;
                    tmp.offer(new Info(x, y, age));
                } else
                    dieQ.offer(new Info(x, y, age));
            }
            treeQ = tmp;
            // 봄

            while (!dieQ.isEmpty()) {
                Info die = dieQ.poll();
                feed[die.x][die.y] += die.age / 2;
            }
            // 여름

            PriorityQueue<Info> tmp2 = new PriorityQueue<>((o1, o2)->{
                return o1.age-o2.age;
            });
            size = treeQ.size();
            while (size-- > 0) {
                Info tree = treeQ.poll();
                tmp2.offer(tree);
                if (tree.age % 5 == 0) {
                    int x = tree.x, y = tree.y;
                    for (int dir = 0; dir < 8; ++dir) {
                        int nx = x + dx[dir], ny = y + dy[dir];
                        if (0 < nx && nx <= n && 0 < ny && ny <= n)
                            tmp2.offer(new Info(nx, ny, 1));
                    }
                }
            }
            treeQ = tmp2;
            // 가을

            for(int i = 1; i <= n; ++i){
                for(int j = 1; j <= n; ++j)
                    feed[i][j] += a[i][j];
            }
            // 겨울
        }
        System.out.println(treeQ.size());
    }

    static class Info{
        int x, y, age;

        public Info(int x, int y, int age) {
            this.x = x;
            this.y = y;
            this.age = age;
        }
    }
}

문제 링크

풀이 )

  서류 성적과 면접 성적 뭐가 되어도 상관 없지만 나는 서류 성적에 대해서 성적이 좋은 순서에서 안좋은 순서로 정렬해줬다.

  1등에 있는 사람은 서류 성적이 누구보다 높기 때문에 항상 뽑힐 수 있다.

  이후에 있는 사람은 1등보다 서류 성적은 떨어지기 때문에 면접 성적은 더 좋아야한다.

  그렇기 때문에 현재의 가장 낮은 면접 성적 커트라인을 cut에 저장하여 커트라인을 통과한다면, 커트라인을 현재 사람의 면접 성적과 비교하여 더 작은 값으로 갱신해주고, 정답을 한명 늘려준다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            int n = Integer.parseInt(br.readLine());
            Point[] scores = new Point[n];
            for(int i = 0; i < n; ++i){
                in = br.readLine().split(" ");
                scores[i] = new Point(Integer.parseInt(in[0]), Integer.parseInt(in[1]));
            }
            Arrays.sort(scores, (o1, o2)->
                o1.x-o2.x
            );
            int ans = 0;
            int cut = (int)1e9;
            for(int i = 0; i < n; ++i){
                int cur = scores[i].y;
                if(cur < cut) {
                    ans++;
                    cut = Math.min(cur, cut);
                }
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}

문제 링크

풀이 ) DFS

  적록색약이 아닌 사람은 R, G, B를 각각 따로 / 적록색약인 사람은 R과G를 구분하지 않고, B만 따로 봐주면 된다.

  각각 다르게 DFS를 구현할 수 있지만 같은 메서드에 대해서 flag를 다르게 넘겨주어 다음 칸이 유효한지 확인하는 부분만 다르게 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n;
    static char[][] board;
    static boolean[][] visited;

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

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

        n = Integer.parseInt(br.readLine());
        board = new char[n][];
        for(int i = 0; i < n; ++i)
            board[i] = br.readLine().toCharArray();

        visited = new boolean[n][n];
        int ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j]){
                    dfs(i, j, board[i][j], false);
                    ans++;
                }
            }
        }
        sb.append(ans).append(' ');

        visited = new boolean[n][n];
        ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j]){
                    dfs(i, j, board[i][j], true);
                    ans++;
                }
            }
        }
        sb.append(ans);
        System.out.println(sb);
    }

    static void dfs(int x, int y, char c, boolean flag){
        visited[x][y] = true;
        for(int dir = 0; dir < 4; ++dir){
            int nx = x+dx[dir], ny = y+dy[dir];
            if(!isIn(nx, ny, c, flag) || visited[nx][ny])
                continue;
            dfs(nx, ny, c, flag);
        }
    }

    static boolean isIn(int x, int y, char c, boolean flag){
        if(flag){
            if(c == 'B')
                return 0 <= x && x < n && 0 <= y && y < n && board[x][y] == 'B';
            else
                return 0 <= x && x < n && 0 <= y && y < n && board[x][y] != 'B';
        }
        return 0 <= x && x < n && 0 <= y && y < n && board[x][y] == c;
    }
}

주의 )

- visited와 ans의 초기화

문제 링크

풀이 )

  맵을 사용하는 기본적인 문제이다.

  숫자 카드에 들어갈 수 있는 값의 범위가 너무 넓기 때문에 범위만큼의 배열을 선언해서 개수를 기록하는 방법으로는 해결할 수 없다.

  입력받는 숫자 카드를 key값으로 하여 해당 key값이 있으면(containsKey) value를 1 올려주고 없으면 key에 1을 넣어준다.

  마지막으로 찾는 key 값에 대해서 key값이 있으면 value를, 없으면 0을 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

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

        int n = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> map = new HashMap<>();
        in = br.readLine().split(" ");
        for(int i = 0; i < n; ++i){
            int key = Integer.parseInt(in[i]);
            if(map.containsKey(key))
                map.put(key, map.get(key)+1);
            else
                map.put(key, 1);
        }

        int m = Integer.parseInt(br.readLine());
        in = br.readLine().split(" ");
        for(int i = 0; i < m; ++i){
            int key = Integer.parseInt(in[i]);
            if(map.containsKey(key))
                sb.append(map.get(key)).append(' ');
            else
                sb.append(0).append(' ');
        }
        System.out.println(sb);
    }
}

문제 링크

풀이 )

  가장 먼저 주사위의 마주보는 면을 짝 지어주기 위해 (0, 3), (1, 4), (2, 5) 인덱스에 각각 마주보는 면을 저장해주었다.

  가장 바닥에 올 수 있는 면은 1번 주사위의 면 6개 중 하나이기 때문에 전체 6가지 답이 나올 수 있다.

  각 주사위에 대해서 밑면의 숫자를 bottom, 윗면의 숫자를 top이라고 하면 이때 가장 큰 답이 나오기 위해서는 위, 아랫면을 제외한 4면 중 가장 큰 값을 선택하면 된다.

  이 값을 구하기 위한 getSide( )메서드에서는

• bottom과 top이 각각 5와 6 또는 6과 5인 경우 (즉, 합이 13) 4를 반환
• bottom 또는 top이 6이고 나머지는 5 미만인 경우 5를 반환
• 그 이외의 경우에는 6을 반환한다.

  이전 주사위의 윗면의 숫자와 일치하는 현재 주사위의 아랫면과 현재 주사위의 윗면을 제외한

  나머지 현재 주사위의 옆면에 대해서도 같은 작업을 반복한다.

  이렇게 구한 값 중 최댓값이 답이 된다.

(마주보는 면의 인덱스를 조건문 처리해주지 않기 위해 i와 (i+3)%6으로 구했다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int n = Integer.parseInt(br.readLine());
        int[][] dice = new int[n][6];
        for(int i = 0; i < n; ++i){
            in = br.readLine().split(" ");
            dice[i][0] = Integer.parseInt(in[0]);
            dice[i][1] = Integer.parseInt(in[1]);
            dice[i][2] = Integer.parseInt(in[2]);
            dice[i][3] = Integer.parseInt(in[5]);
            dice[i][4] = Integer.parseInt(in[3]);
            dice[i][5] = Integer.parseInt(in[4]);
        }

        int max = 0;
        for(int i = 0; i < 6; ++i){
            int bottom = dice[0][i];
            int top = dice[0][(i+3)%6];
            int sum = getSide(bottom, top);
            for(int j = 1; j < n; ++j){
                for(int k = 0; k < 6; ++k){
                    if(dice[j][k] == top){
                        bottom = dice[j][k];
                        top = dice[j][(k+3)%6];
                        break;
                    }
                }
                sum += getSide(bottom, top);
            }
            max = Math.max(max, sum);
        }
        System.out.println(max);
    }

    public static int getSide(int bottom, int top){
        if(bottom+top == 11)
            return 4;
        else if(bottom == 6 || top == 6)
            return 5;
        else
            return 6;
    }
}