반응형

* 핵심 개념

4월 삼성역테 기출문제이다.

1. 3명의 궁수의 위치를 지정하기 위해 m개 가로열 중 3자리 선택(DFS로 구현)

2. 각 궁수의 위치가 정해지면 3명의 궁수를 BFS 탐색

주의1) 같은 길이면 왼쪽에 있는 몬스터를 먼저 잡기 때문에 dx, dy를 왼쪽, 가운데, 오른쪽 순서대로 해야한다.

주의2) 궁수가 같은 몬스터를 공격할 수도 있기 때문에 찾은 몬스터를 바로 0으로 바꾸지 말것

* 문제

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성 위의 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c2), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {0-10};
    public static int[] dy = {-101};
    public static int n, m, d, ans = 0;
    public static boolean[] used;   //nCr 구할 때 사용하는 배열
    public static int[][] map;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());
        d = Integer.parseInt(stk.nextToken());
        map = new int[n + 1][m];
        used = new boolean[m];
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }
        nCr(00);
        System.out.println(ans);
    }
 
    //m개의 자리중 3개의 궁수 자리 선택
    public static void nCr(int idx, int cnt) {
        if (cnt == 3) {
            int[][] nmap = new int[n + 1][m];
            for (int i = 0; i < n + 1; i++) {
                for (int j = 0; j < m; j++) {
                    nmap[i][j] = map[i][j];
                }
            }
            bfs(nmap);
            return;
        }
        for (int i = idx; i < m; i++) {
            if (!used[i]) {
                used[i] = true;
                nCr(i, cnt + 1);
                used[i] = false;
            }
        }
    }
 
    public static void bfs(int[][] nmap) {
        int cnt = 0;
        for (int i = n; i > 0; i--) {   //궁수의 포지션을 한칸씩 앞으로 이동
            int archerIdx = 0;
            Queue<Pair> q = new LinkedList<>();
            for (int j = 0; j < m; j++) {
                //nmap에서 궁수 위치는 2
                if (used[j]) {
                    nmap[i][j] = 2;
                    q.add(new Pair(i - 1, j, 1, archerIdx++));
                } else {    //궁수 위치가 아니면 0
                    nmap[i][j] = 0;
                }
            }
 
            boolean[] isEnemyFind = new boolean[3];     //각 궁수가 몬스터를 찾았는지
            boolean[][][] visited = new boolean[n][m][3];   //각 궁수가 해당 좌표를 방문했는지
            boolean[][] isAlreadyFindLocation = new boolean[n][m];  //이미 다른 궁수가 찾은 목표물인지
            ArrayList<Pair> alist = new ArrayList<>();
 
            while (!q.isEmpty()) {
                Pair p = q.poll();
                if (isEnemyFind[p.idx]) continue;
                if (nmap[p.x][p.y] == 1) {
                    isEnemyFind[p.idx] = true;
                    if (!isAlreadyFindLocation[p.x][p.y]) {
                        isAlreadyFindLocation[p.x][p.y] = true;
                        alist.add(p);
                        cnt++;
                    }
                    continue;
                }
                if (!isEnemyFind[p.idx]) {
                    visited[p.x][p.y][p.idx] = true;
                    for (int j = 0; j < 3; j++) {
                        int nx = p.x + dx[j];
                        int ny = p.y + dy[j];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny][p.idx] && p.depth < d) {
                            q.add(new Pair(nx, ny, p.depth + 1, p.idx));
                        }
                    }
                }
            }
            for (int j = 0; j < alist.size(); j++) {
                Pair p = alist.get(j);
                nmap[p.x][p.y] = 0;
            }
        }
        ans = Math.max(ans, cnt);
    }
 
    public static class Pair {
        int x, y, depth, idx;
 
        public Pair(int x, int y, int depth, int idx) {
            this.x = x;
            this.y = y;
            this.depth = depth;
            this.idx = idx;
        }
    }
}
cs


반응형
반응형

* 핵심 개념

삽질을 상당히 많이한 문제다.

문제를 해석하면 한 방향으로 기울이면 끝까지 이동해야하고 두 구슬이 같은 위치인 경우도 처리가 필요하다.

4%에서 계속 틀렸다고 나왔는데 이유를 알고보니 개념의 실수였다.

구슬의 방문여부를 4차원 배열로 해결해야 하는데, 2차원배열 2개로 해결하려다 보니 당연히 틀릴수밖에 없었다.

이 둘의 차이는 명백하니 실수하지 말아야겠다.


문제 해결 순서는 

빨간 구슬을 한 방향 끝까지 이동 >> 파란 구슬을 한 방향 끝까지 이동 >> 둘이 같은 점이면 많이 움직인 구슬을 한칸 되돌림 >> 새로운 점 큐에 추가


* 문제

문제

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.


* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {1-100};
    public static int[] dy = {001-1};
    public static int n, m;
    public static int rx, ry, bx, by;
    public static int[][] map;
    public static boolean[][][][] visited;
    public static Queue<Pair> q = new LinkedList<>();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());
        map = new int[n + 1][m + 1];
        visited = new boolean[n + 1][m + 1][n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            String s = br.readLine();
            for (int j = 1; j <= s.length(); j++) {
                int tmp = 0;
                switch (s.charAt(j - 1)) {
                    case '#':
                        tmp = -1;
                        break;
                    case '.':
                        tmp = 0;
                        break;
                    case 'R':
                        tmp = 1;
                        rx = i;
                        ry = j;
                        break;
                    case 'B':
                        tmp = 2;
                        bx = i;
                        by = j;
                        break;
                    case 'O':
                        tmp = 3;
                        break;
                }
                map[i][j] = tmp;
            }
        }
        System.out.println(bfs());
    }
 
    public static int bfs() {
        q.add(new Pair(rx, ry, bx, by, 0));
        visited[rx][ry][bx][by] = true;
        while (!q.isEmpty()) {
            Pair p = q.poll();
            if (p.cnt > 10continue;
            if (map[p.bx][p.by] == 3continue;
            if (map[p.rx][p.ry] == 3return p.cnt;
 
            for (int i = 0; i < 4; i++) {
                //빨간 구슬 상하좌우 끝까지 이동
                int next_rx = p.rx, next_ry = p.ry;
                while (true) {
                    //다음 지점이 벽이랑 구멍이 아니면
                    if (map[next_rx][next_ry] != -1 && map[next_rx][next_ry] != 3) {
                        next_rx += dx[i];
                        next_ry += dy[i];
                    } else {
                        //다음 지점이 벽이면
                        if (map[next_rx][next_ry] == -1) {
                            next_rx -= dx[i];
                            next_ry -= dy[i];
                        }
                        break;
                    }
                }
 
                //파란 구슬 상하좌우 끝까지 이동
                int next_bx = p.bx, next_by = p.by;
                while (true) {
                    //다음 지점이 벽이랑 구멍이 아니면
                    if (map[next_bx][next_by] != -1 && map[next_bx][next_by] != 3) {
                        next_bx += dx[i];
                        next_by += dy[i];
                    } else {
                        //다음 지점이 벽이면
                        if (map[next_bx][next_by] == -1) {
                            next_bx -= dx[i];
                            next_by -= dy[i];
                        }
                        break;
                    }
                }
 
                //구한 Red, Blue 의 점이 서로 같은데 'O'가 아닌 경우
                //더 움직인 구슬의 dx[i], dy[i]를 빼준다
                if (next_rx == next_bx && next_ry == next_by) {
                    if (map[next_rx][next_ry] != 3) {
                        int red_cost = Math.abs(next_rx - p.rx) + Math.abs(next_ry - p.ry);
                        int blue_cost = Math.abs(next_bx - p.bx) + Math.abs(next_by - p.by);
                        if (red_cost > blue_cost) {
                            next_rx -= dx[i];
                            next_ry -= dy[i];
                        } else {
                            next_bx -= dx[i];
                            next_by -= dy[i];
                        }
                    }
                }
 
                //next 점이 방문한적 없다면 큐에 추가
                if (!visited[next_rx][next_ry][next_bx][next_by]) {
                    visited[next_rx][next_ry][next_bx][next_by] = true;
                    q.add(new Pair(next_rx, next_ry, next_bx, next_by, p.cnt + 1));
                }
            }
        }
        return -1;
    }
 
    public static class Pair {
        int rx, ry, bx, by, cnt;
 
        public Pair(int rx, int ry, int bx, int by, int cnt) {
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.cnt = cnt;
        }
    }
}
cs


반응형
반응형

* 핵심 개념

고려해야 할 사항은 크게 두가지다.

1. 물고기가 같은 거리에 있는 경우 위에 있고, 왼쪽에 있는 물고기를 먹는다. 

다른 방법도 존재하지만 우선순위 큐를 사용하여 처리하였다. (148ms)

먹이를 찾았을 때 큐에 남은 점들을 다시 확인해서 비교한다. (80ms)

2. 물고기를 먹고 나서 상어 크기가 증가하는 지 확인해야 한다.

하나 주의해야 할 점은 상어의 위치를 받고 map을 0으로 변경해주는 작업도 필요하다.


요약하면, 

상어 위치 확인  >> 물고기 탐색(BFS) >> 찾은 물고기 우선순위 큐에 저장 >> 우선순위 큐의 맨 앞 물고기 선택 >> 상어 위치 변경 및 상어 크기 증가여부 확인

상어 위치 확인 >> 물고기 탐색(BFS) >> 물고기 찾으면 남아있는 큐 탐색 >> 최적의 물고기 위치 확인 >> 상어 위치 변경 및 상어 크기 증가 여부 확인

위 순서대로 진행하며 BFS가 끝낫는데 큐의 크기가 0이라면 먹을 수 있는 물고기가 없다는 뜻이므로 움직인 거리를 출력하면 된다.

* 문제

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최소값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {-1001};
    public static int[] dy = {0-110};
    public static int n, eating = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        Queue<Shark> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == 9) {
                    q.add(new Shark(i, j, 20));
                    map[i][j] = 0;
                }
            }
        }
 
        int ans = 0;
        boolean[][] visited = new boolean[n][n];
        while (!q.isEmpty()) {
            Shark shark = q.poll();
            if (!visited[shark.x][shark.y]) {
                visited[shark.x][shark.y] = true;
                if (map[shark.x][shark.y] != 0 && map[shark.x][shark.y] < shark.power) {  //상어가 먹이를 찾으면
                    Shark curr = shark;
                    //거리 > 높이 > 왼쪽 순서로 먹기 위해 남은 Queue 탐색
                    while (!q.isEmpty()) {
                        shark = q.poll();
                        if (map[shark.x][shark.y] != 0 && map[shark.x][shark.y] < shark.power) {
                            if (curr.cost == shark.cost) {
                                if (curr.x > shark.x) {
                                    curr = shark;
                                } else if (curr.x == shark.x && curr.y > shark.y) {
                                    curr = shark;
                                }
                            } else if (curr.cost > shark.cost) {
                                curr = shark;
                            }
                        }
                    }
                    map[curr.x][curr.y] = 0;
                    eating++;
                    ans += curr.cost;
                    int flag = 0;
                    if (eating == curr.power) {        //상어가 성장할 수 있으면
                        flag = 1;
                        eating = 0;
                    }
                    q.clear();
                    q.add(new Shark(curr.x, curr.y, curr.power + flag, 0));
                    visited = new boolean[n][n];
                    continue;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = shark.x + dx[i];
                    int ny = shark.y + dy[i];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && map[nx][ny] <= shark.power && !visited[nx][ny]) {
                        q.add(new Shark(nx, ny, shark.power, shark.cost + 1));
                    }
                }
            }
        }
        System.out.println(ans);
    }
 
    public static class Shark {
        int x, y, power, cost;
 
        public Shark(int x, int y, int power, int cost) {
            this.x = x;
            this.y = y;
            this.power = power;
            this.cost = cost;
        }
    }
}
cs


반응형