백준 20058, 프로그래머스 - 섬 연결하기, 보석쇼핑

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

20058번: 마법사 상어와 파이어스톰

* 삼성 기출문제 (시뮬레이션, 구현, 탐색) 

 

1. 단계를 입력받고 칸을 나눈다. 참고로 이때 바로 원본배열에 적용하면 안된다. (동시에 녹이고 반영해야하므로)

2. 각 격자를 회전시키는 함수 수행 

3. 얼음 녹이기 (모든 얼음은 동시에 녹아야 한다!!!! 꼭 기억할 것!)

4. 다 끝나면 덩어리 출력

 

이런 문제의 경우 미리 각 움직임을 dirX, dirY 배열에 정의해두면 편하다.

! 배열을 회전하는 함수도 종종 문제에서 출제되므로 이번 기회에 외워두기 

! 얼음 한번에 녹는다는 것을 꼭 기억. 바로 원본배열 건드리면 안된다. 삼성기출에서 이런 유형이 자주 나온다. 

public class p20058 {
    public static int[][] graph;
    public static int[] step;
    public static int[] dirX = { 0, 1, 0, -1 };
    public static int[] dirY = { -1, 0, 1, 0 };
    public static int size, answerIce, answerSize;

    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 q = Integer.parseInt(st.nextToken());
        size = (int) Math.pow(2, n);
        graph = new int[size][size];
        for (int i = 0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < size; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        step = new int[q];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < q; i++) {
            step[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < q; i++) {
            graph = divide(step[i]); // 단계에 맞게 칸 나누고 회전 시키기
            graph = melt(); // 녹인 결과 저장
        }
        answerIce = answerSize = 0;
        find();

        System.out.println(answerIce);
        System.out.println(answerSize);


    }

    public static int[][] divide(int steps) {
        int[][] temp = new int[size][size];
        steps = (int) Math.pow(2, steps);
        for (int i = 0; i < size; i += steps) {
            for (int j = 0; j < size; j += steps) {
                rotateRight(i, j, steps, temp);
            }
        }
        return temp;
    }

    public static void rotateRight(int x, int y, int size, int[][] temp) {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                temp[x+i][y+j] = graph[x+size-1-j][y+i];
            }
        }
    }

    public static int[][] melt() {
        int[][] temp = new int[size][size];
        for (int i = 0; i < size; i++) {
            temp[i] = Arrays.copyOf(graph[i], size);
        }
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int count = 0;
                if (graph[i][j] == 0) {
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    int nextX = i + dirX[k];
                    int nextY = j + dirY[k];
                    if (nextX >= 0 && nextX < size && nextY >= 0 && nextY < size && graph[nextX][nextY] > 0) {
                        count++;
                    } // 현 좌표에서 4방향 탐색. 유효 범위내 좌표이고, 얼음이 있다면 count 증가
                }
                if (count < 3) {
                    temp[i][j]--; 
                }
            }
        }
        return temp;
    }

    public static void find() {
        Queue<Pos> queue = new LinkedList<>();
        boolean[][] visited = new boolean[size][size];

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                answerIce += graph[i][j]; // 모든 칸의 얼음 다 더한값이 answerIce
                if (graph[i][j] > 0 && !visited[i][j]) {
                    queue.offer(new Pos(i, j));
                    visited[i][j] = true;
                    int count = 1;

                    while (!queue.isEmpty()) {
                        Pos pos = queue.poll();

                        for (int k = 0; k < 4; k++) {
                            int nextX = pos.x + dirX[k];
                            int nextY = pos.y + dirY[k];
                            if (nextX >= 0 && nextX < size && nextY >= 0 && nextY < size && graph[nextX][nextY] > 0 && !visited[nextX][nextY]) {
                                queue.offer(new Pos(nextX, nextY));
                                visited[nextX][nextY] = true;
                                count++;
                            }
                        }
                    }
                    answerSize = Math.max(answerSize, count); // 가장 큰 얼음 칸 개수
                }
            }
        }

    }

    static class Pos {
        int x;
        int y;
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

* Greedy 알고리즘 

* 우선순위큐에 넣어서 자동으로 에지 값 순서로 정렬시키고(에지 가중치 작은 순 정렬) 하나씩 꺼내면서 다리를 놓는다. 다리를 놓을 수 있는 최대 개수는 노드-1이므로 edgeCount값을 n-1로 지정해놓은 것. (노드-1인 경우는 일직선으로 쭉 연결된 경우) 

 

import java.util.*;
public class 섬연결하기 {
    class Solution {
        public int[] union;
        public int solution(int n, int[][] costs) {
            PriorityQueue<Edge> queue = new PriorityQueue<>();
            union = new int[n];
            int edgeCount = n-1;
            int answer = 0;

            for (int i = 0; i < n; i++) {
                union[i] = i;
            }
            for (int i = 0; i < costs.length; i++) {
                queue.add(new Edge(costs[i][0], costs[i][1], costs[i][2]));
            }


            while (edgeCount > 0) {
                Edge e = queue.poll();
                int a = findNode(e.start);
                int b = findNode(e.end);
                if (a != b) {
                    unionNode(a, b);
                    answer += e.weight;
                    edgeCount--;
                }
            }
            return answer;
        }

        public void unionNode(int a, int b) {
            int findA = findNode(a);
            int findB = findNode(b);
            if (findA != findB) {
                union[findB] = findA;
            }
        }

        public int findNode (int n) {
            if (union[n] == n) {
                return n;
            } else {
                return union[n] = findNode(union[n]);
            }
        }

        public class Edge implements Comparable<Edge> {
            int start;
            int end;
            int weight;

            public Edge (int s, int e, int w) {
                this.start = s;
                this.end = e;
                this.weight = w;
            }

            public int compareTo(Edge e) {
                return this.weight < e.weight ? -1 : 1;
            }

        }
    }
}

 

 

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/67258

프로그래머스

* two-pointer 알고리즘 문제 

* Set, Map 에 대해 알고 있을 것.

중복 없이 각 값만 저장하고, 순서는 중요하지 않으므로 Set 사용.

각 보석별 개수는 Map에 저장. (보석종류, 개수)의 형태로 저장한다. 

 

 

import java.util.*;
public class 보석쇼핑 {
    class Solution {
        public int[] solution(String[] gems) {
            int start = 0;
            int end = 0;
            int startAnswer = 0;
            int endAnswer = gems.length-1;

            // 보석 종류를 먼저 저장해두기, 종류 그 자체를 저장하므로 HashSet
            Set<String> gemType = new HashSet<>(Arrays.asList(gems));
            Map<String, Integer> tempGem = new HashMap<>();

            tempGem.put(gems[start], 1);
            while (start < gems.length) {
                if (tempGem.keySet().size() == gemType.size()) { // 현재 모든 보석이 다 들어있다면
                    if (end - start < endAnswer - startAnswer) {
                        startAnswer = start;
                        endAnswer = end;
                    } // 현재 거리가 더 짧다면 startAnswer, endAnswer 갱신 
                    // 시작점 옮겨주고 시작점 보석을 줄임
                    tempGem.put(gems[start], tempGem.get(gems[start]) - 1);
                    // 0개라면 해당 보석 종류 제거
                    if (tempGem.get(gems[start]) == 0) {
                        tempGem.remove(gems[start]);
                    }
                    start++;
                }
                else if (end < gems.length - 1) { // 그게 아니라면 end를 뒤로 보내서 한 칸씩 늘린다
                    end++;
                    if (tempGem.get(gems[end]) == null) {
                        tempGem.put(gems[end], 1);
                    }
                    else {
                        tempGem.put(gems[end], tempGem.get(gems[end]) + 1);
                    }

                }
                else {
                    break;
                }
            }
            return new int[] { startAnswer + 1, endAnswer+1 };
        }
    }
}