더 이상 물러설 곳이 없다

www.acmicpc.net/problem/11286

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1

18

1

-1

0

0

0

1

1

-1

-1

2

-2

0

0

0

0

0

0

0

예제 출력 1

-1

1

0

-1

-1

1

1

-2

2

0

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

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

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((o1, o2) -> {
            int abs1 = Math.abs(o1);
            int abs2 = Math.abs(o2);
            if (abs1 != abs2) {
                if (abs1 < abs2) return -1;
                else return 1;
            } else {
                if (o1.intValue() < o2.intValue()) return -1;
                else return 1;
            }
        });

//        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                int abs1 = Math.abs(o1);
//                int abs2 = Math.abs(o2);
//                if(abs1 != abs2) {
//                    if(abs1 < abs2) return -1;
//                    else return 1;
//                }else {
//                    if(o1.intValue() < o2.intValue()) return -1;
//                    else return 1;
//                }
//            }
//        });

        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            int input = Integer.parseInt(br.readLine());
            if(input != 0) {
                pq.add(input);
            }else {
                if(pq.isEmpty()) {
                    sb.append("0\n");
                }else {
                    sb.append(pq.poll() + "\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}

우선순위 큐의 정렬 조건을 따로 설정해주면 된다.

new Comparator() 대신 람다식을 사용해서 처리했다.

www.acmicpc.net/problem/15683

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0

0 0 0 0 0 0

0 0 1 0 6 0

0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 벽을 감시할 수 없다.

0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 6 0 0 6 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3 0 6 0 0 0 0 0 6 6 0 0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3 0 6 # 0 # 0 0 6 6 # 0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

예제 입력 1

4 6

0 0 0 0 0 0

0 0 0 0 0 0

0 0 1 0 6 0

0 0 0 0 0 0

예제 출력 1

20

예제 입력 2

6 6

0 0 0 0 0 0

0 2 0 0 0 0

0 0 0 0 6 0

0 6 0 0 2 0

0 0 0 0 0 0

0 0 0 0 0 5

예제 출력 2

15

예제 입력 3

6 6

1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1

예제 출력 3

6

예제 입력 4

6 6

1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 5 0 0

0 0 5 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1

예제 출력 4

2

예제 입력 5

1 7

0 1 2 3 4 5 6

예제 출력 5

0

예제 입력 6

3 7

4 0 0 0 0 0 0

0 0 0 2 0 0 0

0 0 0 0 0 0 4

예제 출력 6

0

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Pair {
    int r, c, cctv, dir;
    Pair(int r, int c, int cctv, int dir) {
        this.r = r;
        this.c = c;
        this.cctv = cctv;
        this.dir = dir;
    }
}

public class Main {
    static int n, m, k, ans = Integer.MAX_VALUE;
    static ArrayList<Pair> cList;
    static int[][] map;
    static int[][] temp;
    static int[] rArr = {-1, 0, 1, 0};  // 북동남서
    static int[] cArr = {0, 1, 0, -1};

    public static void calculate() {
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(temp[i][j] == 0)
                    cnt += 1;
            }
        }
        ans = Math.min(ans, cnt);
    }

    public static void fillArr(int nr, int nc, int dir) {
        while(-1 < nr && nr < n && -1 < nc && nc < m && map[nr][nc] != 6) {
            temp[nr][nc] = 7;
            nr += rArr[dir];
            nc += cArr[dir];
        }
    }

    public static void monitor() {
        for(int i = 0; i < n; i++) {  // 메모리 down, 시간 up
            for(int j = 0; j < m; j++) {
                temp[i][j] = map[i][j];
            }
        }
        
//        for(int i = 0; i < n; i++) {  // 메모리 up, 시간 down
//            temp[i] = map[i].clone();
//        }

        // 7이면 감시 영역
        for(Pair p : cList) {
            int nr = p.r, nc = p.c, dir = p.dir;
            switch(p.cctv) {
                case 1 :
                    fillArr(nr, nc, dir);
                    break;
                case 2 :
                    fillArr(nr, nc, dir);
                    nr = p.r; nc = p.c;
                    dir = (dir + 2) % 4;
                    fillArr(nr, nc, dir);
                    break;
                case 3 :
                    for(int i = 0; i < 2; i++) {
                        nr = p.r; nc = p.c;
                        dir = (dir + i) % 4;
                        fillArr(nr, nc, dir);
                    }
                    break;
                case 4 :
                    for(int i = 0; i < 3; i++) {
                        nr = p.r; nc = p.c;
                        dir = (dir + i) % 4;
                        fillArr(nr, nc, dir);
                    }
                    break;
                case 5 :
                    for(int i = 0; i < 4; i++) {
                        nr = p.r; nc = p.c;
                        dir = (dir + i) % 4;
                        fillArr(nr, nc, dir);
                    }
                    break;
            }
        }
    }

    public static void dfs(int dept) {
        if(dept == k) {
            monitor();
            calculate();
            return;
        }

        Pair p = cList.get(dept);
        switch(p.cctv ) {
            case 2 :
                p.dir = 0; dfs(dept + 1);
                p.dir = 1; dfs(dept + 1);
                break;
            case 5 :
                p.dir = 0; dfs(dept + 1);
                break;
            default :
                p.dir = 0; dfs(dept + 1);
                p.dir = 1; dfs(dept + 1);
                p.dir = 2; dfs(dept + 1);
                p.dir = 3; dfs(dept + 1);
                break;
        }
    }

    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());

        map = new int[n][m];
        temp = new int[n][m];
        cList = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(1 <= map[i][j] && map[i][j] <= 5) {
                    cList.add(new Pair(i, j, map[i][j], 0));
                }
            }
        }
        k = cList.size();

        dfs(0);
        System.out.println(ans);
    }
}

브루트 포스 + 구현 문제.

cctv의 개수는 최대 8개, 최대 4방향 검사 가능 -> 4^8가지 경우의 수 (약 64,000개)

브루트 포스 가능

1. 카메라들이 방향을 모두 정한다.

2. 각 감시 방향을 모두 채운다.

3. 다 채웠으면 사각지대 개수를 센다.

www.acmicpc.net/problem/2776

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에  ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

예제 입력 1

1

5

4 1 5 2 3

5

1 3 7 9 5

예제 출력 1

1

1

0

0

1

풀이 1. (틀린 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        while(T-- > 0) {
            StringBuilder sb = new StringBuilder();
            Set<Integer> note1 = new HashSet<>();
            Set<Integer> note2 = new LinkedHashSet<>();

            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < n; i++) {
                note1.add(Integer.parseInt(st.nextToken()));
            }
            int m = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < m; i++) {
                note2.add(Integer.parseInt(st.nextToken()));
            }

            for(int num : note2) {
                if(note1.contains(num)) {
                    sb.append("1\n");
                }else {
                    sb.append("0\n");
                }
            }
            System.out.println(sb.toString());
        }
    }
}

Set의 특성을 제대로 생각하지 않고 풀어서 틀렸다.

1. Set은 중복 원소는 저장하지 않는다.

-> 그렇기 때문에 note2에 전부 저장한 후 하나씩 뽑아낼 경우 m개의 질문 중 중복되는 값이 있다면 m개 이하의 답이 출력되어버릴 수 있다.

2. Set은 입력 순서를 보장하지 않는다.

-> Set은 기본적으로 입력 순서를 보장하지 않고 오름차순으로 값을 저장한다. 이 때문에 값들의 저장을 일괄적으로 수행한 후 검사를 하면 출력값의 순서가 올바르지 못하게 된다.

(순서 유지를 원한다면 LinkedHashSet을 쓰면 된다.)

이를 해결하기 위해 그냥 m개의 수를 입력 받자마자 검사를 실시했다.

풀이 2. (정답 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(st.nextToken());

        while(T-- > 0) {
            Set<Integer> note = new HashSet<>();
            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < n; i++) {
                note.add(Integer.parseInt(st.nextToken()));
            }

            int m = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < m; i++) {
                int num = Integer.parseInt(st.nextToken());
                if(note.contains(num)) {
                    sb.append("1\n");
                }else {
                    sb.append("0\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}

Set을 하나만 사용하고 m개의 숫자를 입력 받자마자 검사하여 해결.

www.acmicpc.net/problem/1269

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때,  A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.

입력

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.

출력

첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

예제 입력 1

3 5

1 2 4

2 3 4 5 6

예제 출력 1

4

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

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

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        Set<Integer> setA = new HashSet<>();
        Set<Integer> setB = new HashSet<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < a; i++) {
            setA.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < b; i++) {
            setB.add(Integer.parseInt(st.nextToken()));
        }

        int ans = 0;
        for(int num : setA) {
            if(!setB.contains(num)) {
                ans += 1;
            }
        }
        for(int num : setB) {
            if(!setA.contains(num)) {
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

Hash의 짧은 검색시간을 활용하는 문제.

set.contain() == O(1)

www.acmicpc.net/problem/10546

문제

마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명만 빼고! 

모두가 참가하고 싶어서 안달인데 이런 백준 마라톤 대회에 참가해 놓고 완주하지 못한 배부른 참가자 한 명은 누굴까?

입력

첫째 줄에는 참가자 수 N이 주어진다. (1 ≤ N ≤ 105)

N개의 줄에는 참가자의 이름이 주어진다.

추가적으로 주어지는 N-1개의 줄에는 완주한 참가자의 이름이 쓰여져 있다. 

참가자들의 이름은 길이가 1보다 크거나 같고, 20보다 작거나 같은 문자열이고, 알파벳 소문자로만 이루어져 있다.

참가자들 중엔 동명이인이 있을 수도 있다. 

출력

마라톤을 완주하지 못한 참가자의 이름을 출력한다.

예제 입력 1

3

leo

kiki

eden

eden

kiki

예제 출력 1

leo

예제 입력 2

5

marina

josipa

nikola

vinko

filipa

josipa

filipa

marina

nikola

예제 출력 2

vinko

예제 입력 3

4

mislav

stanko

mislav

ana

stanko

ana

mislav

예제 출력 3

mislav

풀이 .

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

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

        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            String key = br.readLine();
            if(map.get(key) == null) {
                map.put(key, 1);
            }else {
                map.put(key, map.get(key) + 1);
            }
        }

        for(int i = 0; i < n-1; i++) {
            String key = br.readLine();
            map.put(key, map.get(key) - 1);
        }

        for(String key : map.keySet()) {
            if(map.get(key) != 0) {
                System.out.println(key);
                break;
            }
        }
    }
}

프로그래머스의 '완주하지 못한 선수'와 똑같은 문제.

HashMap으로 간단히 해결할 수 있다.

www.acmicpc.net/problem/1302

문제

김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.

오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.

예제 입력 1

5

top

top

top

top

kimtop

예제 출력 1

top

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            if(map.get(str) == null) {
                map.put(str, 1);
            }else {
                map.put(str, map.get(str) + 1);
            }
        }

        int val = 0;
        String ans = "";
        for(String key : map.keySet()) {
            if(val == map.get(key)) {
                if(ans.compareTo(key) > 0) {
                    ans = key;
                }
            }else if(val < map.get(key)) {
                val = map.get(key);
                ans = key;
            }

        }
        System.out.println(ans);
    }
}

HashMap을 사용해 쉽게 풀 수 있다.

www.acmicpc.net/problem/15686

문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0

1 0 1 0 0

0 0 0 0 0

0 0 0 1 1

0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

예제 입력 1

5 3

0 0 1 0 0

0 0 2 0 1

0 1 2 0 0

0 0 1 0 0

0 0 0 0 2

예제 출력 1

5

예제 입력 2

5 2

0 2 0 1 0

1 0 1 0 0

0 0 0 0 0

2 0 0 1 1

2 2 0 1 2

예제 출력 2

10

예제 입력 3

5 1

1 2 0 0 0

1 2 0 0 0

1 2 0 0 0

1 2 0 0 0

1 2 0 0 0

예제 출력 3

11

예제 입력 4

5 1

1 2 0 2 1

1 2 0 2 1

1 2 0 2 1

1 2 0 2 1

1 2 0 2 1

예제 출력 4

32

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

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

public class Main {
    static int n, m, ans = Integer.MAX_VALUE;
    static int[][] map;  // 사실 이건 굳이 안 써도 된다
    static boolean[] check;
    static ArrayList<Pair> stores;  // 치킨집들의 좌표
    static ArrayList<Pair> houses;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    public static int calculate() {  // 집과 치킨집 매핑 후 도시의 치킨 거리 계산
        int sum = 0;
        for(int i = 0; i < houses.size(); i++) {
            int hr = houses.get(i).r;
            int hc = houses.get(i).c;
            int dist = Integer.MAX_VALUE;

            for(int j = 0; j < stores.size(); j++) {
                if(check[j]) {
                    int sr = stores.get(j).r;
                    int sc = stores.get(j).c;
                    dist = Math.min(dist, Math.abs(hr - sr) + Math.abs(hc - sc));
                }
            }
            sum += dist;
        }
        return sum;
    }

    public static void dfs(int dept, int idx) {  // 치킨집 m개 조합
        if(dept == m) {
            ans = Math.min(ans, calculate());
            return;
        }

        for(int i = idx; i < stores.size(); i++) {
            // 남은 거 다 뽑아도 m개 채우지 모한다면 더 이상 재귀하지 않음
            if(!check[i] && m - dept <= stores.size() - idx) {
                check[i] = true;
                dfs(dept+1, i+1);
                check[i] = false;
            }
        }
    }

    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());
        map = new int[n][n];
        stores = new ArrayList<>();
        houses = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 2) {
                    stores.add(new Pair(i, j));
                }else if(map[i][j] == 1) {
                    houses.add(new Pair(i, j));
                }
            }
        }
        check = new boolean[stores.size()];

        dfs(0, 0);
        System.out.println(ans);
    }
}

브루트포스 + 구현

그냥 무작정 브루트포스를 때리면 시간 초과가 난다.

얼추 계산해봤을때 충분히 1초 안에 가능할 거 같아서 그렇게 짰는데.. 좀 넘치나보다.

좀 더 똑똑한(?) 브루트포스로 짜야 한다.

다음 치킨집을 선정할 때 check 외에 추가 조건과 int idx를 사용해서 시간 초과를 막았다.

if(!check[i] && m - dept <= stores.size() - idx) 

www.acmicpc.net/problem/14503

문제

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

출력

로봇 청소기가 청소하는 칸의 개수를 출력한다.

예제 입력 1

3 3

1 1 0

1 1 1

1 0 1

1 1 1

예제 출력 1

1

예제 입력 2

11 10

7 4 0

1 1 1 1 1 1 1 1 1 1

1 0 0 0 0 0 0 0 0 1

1 0 0 0 1 1 1 1 0 1

1 0 0 1 1 0 0 0 0 1

1 0 1 1 0 0 0 0 0 1

1 0 0 0 0 0 0 0 0 1

1 0 0 0 0 0 0 1 0 1

1 0 0 0 0 0 1 1 0 1

1 0 0 0 0 0 1 1 0 1

1 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 1 1

예제 출력 2

57

풀이 .

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

public class Main {
    static int n, m, ans;
    static int[][] map;
    static boolean[][] check;
    static int[] rArr = {-1, 0, 1, 0};  // 0123 == 북동남서
    static int[] cArr = {0, 1, 0, -1};

    public static void dfs(int r, int c, int d) {
        int nd = d;  // 현재 방향 d는 유지해야함. 다 돌고 나서 뒷칸으로 이동하는 경우를 위해.
        for (int i = 0; i < 4; i++) {
            // 방향 전환
            nd -= 1;  // 왼쪽 방향
            if (nd == -1) nd = 3;

            int nr = r + rArr[nd];
            int nc = c + cArr[nd];
            if (-1 < nr && nr < n && -1 < nc && nc < m) {
                if (!check[nr][nc] && map[nr][nc] == 0) {
                    check[nr][nc] = true;
                    ans += 1;
                    dfs(nr, nc, nd);
                    return;  // 나머지 방향들은 어차피 이 칸을 뒷칸으로 하여 돌아오는 재귀에서 수행하게 된다
                }
            }
        }

        nd = d - 2;  // 뒷칸
        if (nd == -1) nd = 3;
        if (nd == -2) nd = 2;

        int nr = r + rArr[nd];
        int nc = c + cArr[nd];
        if(-1 < nr && nr < n && -1 < nc && nc < m && map[nr][nc] != 1) {  // 뒷칸으로 갈 수 있는지?
            // 여기선 ans += 1, check[][] = true 해주면 안 됨
            // 지우면서 갈 수 있는 칸이라면 위의 for문에서 재귀했을것임
            // 이 경우는 지우지 않고 단순히 칸만 뒤로 이동하는 경우임
            dfs(nr, nc, d);  // 방향은 유지하면서 칸만 뒤로 이동
        }
    }

    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());

        st = new StringTokenizer(br.readLine());
        int startR = Integer.parseInt(st.nextToken());
        int startC = Integer.parseInt(st.nextToken());
        int startD = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        check = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        check[startR][startC] = true;
        ans += 1;  // 최초 위치는 항상 빈칸임을 보장
        dfs(startR, startC, startD);
        System.out.println(ans);
    }
}

너무 어려웠다.

for문에서 재귀를 수행한 후에 반드시 return 해줘야 한다.

아직 검사하지 않은 방향이 있다고 해도 해당 칸을 뒷칸으로 두는 다른 칸에서 뒤로 돌아오는 재귀를 수행한 후에 마저 검사하기 때문에 더 이상 반복을 돌 필요가 없다.

사실 반복을 더 돌 필요가 없다는 건 이해했지만, "더 돌면 안 되는 이유"는 이해하지 못했다.

너무 어렵다...