반응형

* 형변환

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {
    public static void main(String[] args) throws Exception {
        int a = 65;
        System.out.println("Integer to Character : " + (char) a);           //A
        System.out.println("Integer to String : " + String.valueOf(a));     //65
 
        char ch = '3';
        char[] ch2 = {'a','b'};
        System.out.println("Character to Integer : " + ((int) ch - '0'));   //3
        System.out.println("Character to String : " + String.valueOf(ch));  //3
        System.out.println("Character to String : " + String.valueOf(ch2)); //ab
 
        String s = "9";
        String s2 = "123";
        System.out.println("String to Integer : " + Integer.parseInt(s));   //9
        System.out.println("String to Character : " + s.charAt(0));         //9
        System.out.println("String to Character : " + Arrays.toString(s2.toCharArray()));   // [1, 2, 3]
    }
}
cs

 

스텍

Stack<Integer> stack = new Stack<>(); //int형 스택 선언

push
pop

Queue<Integer> queue = new LinkedList<>();

add
poll

우선순위 큐

PriorityQueue<Integer> pq = new PriorityQueue<>(); 

add 
pop
peek

Array

int[] arr = new int[4];

Arrays.sort();
Arrays.sort(arr, Collections.reverseOrder());
arr.length

 

ArrayList

ArrayList<Integer> alist = new ArrayList<>();

add
remove
get
alist.size();

String[] array = arrayList.toArray(new String[arrayList.size()]);	// ArrayList -> Array
ArrayList<String> arrayList = new ArrayList<>(Arrays.asList(array));	// Array -> ArrayList

HashSet

HashSet hs = new HashSet<>();

add(key)
contains(key)


HashMap

HashMap<String, Integer> hm = new HashMap<>();

put(key, value)
get(key)
containsKey(key)

 

 

 

 

반응형
반응형

* 핵심 개념

음수 가중치가 존재하는 경우 최단 거리를 찾기 때문에 다익스트라가 아닌 벨만포드 알고리즘을 사용해야 한다.

방향이 있는 유향그래프이기 때문에 1번 정점에서부터 시작해서

해당 정점을 갈 수 있는 최단 거리와 이전 정점까지 가중치 + 해당 정점 방문에 필요한 가중치를 더해

최소값을 저장해주면 된다.

* 문제

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -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
import java.io.*;
import java.util.*;
 
public class Main {
    static int[] dist = new int[501];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());
        Edge[] edge = new Edge[m + 1];
 
        // 시작점에서 각 정점으로 가는 최단 거리 저장 배열 초기화
        for (int i = 1; i <= n; i++) dist[i] = Integer.MAX_VALUE;
 
        for (int i = 1; i <= m; i++) {
            stk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());
            int w = Integer.parseInt(stk.nextToken());
            edge[i] = new Edge(u, v, w);
 
        }
        dist[1= 0;        // 1번 정점이 시작점, 시작점까지의 최단거리는 0
        for (int i = 1; i < n; i++) {       // 정점의 수 - 1 번 수행
            for (int j = 1; j <= m; j++) {  // 모든 간선을 사용하여 최단거리가 줄어들면 정보 갱신
                Edge curr = edge[j];
                //u로 가는 최단거리가 바뀌고(무한이 아니고)
                //v로 가는 최단거리 > u까지 필요한 가중치(dist[curr.u]) + u->v 간선 가중치(curr.w)
                if (dist[curr.u] != Integer.MAX_VALUE && dist[curr.v] > dist[curr.u] + curr.w) {
                    dist[curr.v] = dist[curr.u] + curr.w;
                }
            }
        }
 
        // 음수 cycle 확인
        // 만약 음수 cycle이 없다면 시작점에서 모든 점으로 가는 최단거리는 갱신되어 있어야 한다.
        for (int j = 1; j <= m; j++) {
            // 만약 갱신되는 간선이 있다면 음수 cycle 존재
            if (dist[edge[j].u] != Integer.MAX_VALUE && dist[edge[j].v] > dist[edge[j].u] + edge[j].w) {
                bw.write("-1");
                bw.flush();
                bw.close();
                return;
            }
        }
 
        for (int i = 2; i <= n; i++) {
            if (dist[i] != Integer.MAX_VALUE) {
                bw.write(dist[i] + "\n");
            } else {
                bw.write("-1\n");
            }
        }
        bw.flush();
        bw.close();
    }
 
    public static class Edge {
        int u, v, w;
 
        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}
cs


반응형
반응형

Java를 사용하다 보면 형변환할 일이 많이 있다.

int <> char <> String 으로의 형변환에 대해 알아보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {
    public static void main(String[] args) throws Exception {
        int a = 65;
        System.out.println("Integer to Character : " + (char) a);           //A
        System.out.println("Integer to String : " + String.valueOf(a));     //65
 
        char ch = '3';
        char[] ch2 = {'a','b'};
        System.out.println("Character to Integer : " + ((int) ch - '0'));   //3
        System.out.println("Character to String : " + String.valueOf(ch));  //3
        System.out.println("Character to String : " + String.valueOf(ch2)); //ab
 
        String s = "9";
        String s2 = "123";
        System.out.println("String to Integer : " + Integer.parseInt(s));   //9
        System.out.println("String to Character : " + s.charAt(0));         //9
        System.out.println("String to Character : " + Arrays.toString(s2.toCharArray()));   // [1, 2, 3]
    }
}
cs

< 유의 사항 >

char to int에서 숫자를 넘기는 경우 '0'을 해야 한다. (아스키코드값을 넘기기 때문)

char to string에서 char배열인 경우 String.valueOf를 사용하면 char배열 글자가 서로 붙어서 문자열로 넘어간다.

String to char에서 문자 길이가 1이라면 charAt으로 넘기면 된다.

String to char에서 문자 길이가 2이상이라면 toCharArray를 이용해 char배열로 넘긴다.

반응형
반응형

* 핵심 개념

시험 당시에는 17143번 낚시왕 문제보다 복잡해보여서 풀지 않았는데,

다시 풀어보니 역시 풀만한 문제였다. 

특별한 알고리즘 기법이 필요없이 단순히 새로운 크기의 맵을 하나 더 만들어서

새로운 맵에 시뮬레이션한 결과를 저장하고 이를 다시 원래맵에 돌려주기만 하면 된다.

* 문제

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

  1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
    • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
    • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
    • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
    • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
  2. 공기청정기가 작동한다.
    • 공기청정기에서는 바람이 나온다.
    • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
    • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
    • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

* 소스 코드

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
135
136
137
138
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static Cleaner[] cleaner_pos = new Cleaner[2];   //공기청정기 위치 저장
    public static int r, c, t;
    public static int[][] map;
    public static int[] dx = {1-100};
    public static int[] dy = {001-1};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        r = Integer.parseInt(stk.nextToken());
        c = Integer.parseInt(stk.nextToken());
        t = Integer.parseInt(stk.nextToken());
        map = new int[r][c];
        int idx = 0;
        for (int i = 0; i < r; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == -1) {
                    cleaner_pos[idx++= new Cleaner(i, j);
                }
            }
        }
        for (int i = 0; i < t; i++) {
            spreadStart(new int[r][c]);
            cleanerStart(new int[r][c]);
        }
        getAns();
    }
 
    public static void spreadStart(int[][] nmap) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                nmap[i][j] += map[i][j];
                if (map[i][j] < 5continue;
                int spreadCnt = map[i][j] / 5;
                for (int k = 0; k < 4; k++) {
                    int ny = i + dy[k];
                    int nx = j + dx[k];
                    //해당 맵에 퍼트릴 수 있는지 확인
                    if (ny >= 0 && ny < r && nx >= 0 && nx < c && map[ny][nx] != -1) {
                        nmap[i][j] -= spreadCnt;
                        nmap[ny][nx] += spreadCnt;
                    }
                }
            }
        }
        spreadCopy(nmap);
    }
 
    public static void cleanerStart(int[][] nmap) {
        for (int idx = 0; idx < 2; idx++) {
            Cleaner curr = cleaner_pos[idx];
            int ny = curr.r;
            int nx = curr.c + 1;
            //오른쪽으로 끝까지
            while (nx < c - 1) {
                nmap[ny][nx + 1= map[ny][nx];
                nx++;
            }
            //상하로 끝까지
            if (idx == 0) {
                while (ny > 0) {
                    nmap[ny - 1][nx] = map[ny][nx];
                    ny--;
                }
            } else {
                while (ny < r - 1) {
                    nmap[ny + 1][nx] = map[ny][nx];
                    ny++;
                }
            }
            //좌측으로 끝까지
            while (nx > 0) {
                nmap[ny][nx - 1= map[ny][nx];
                nx--;
            }
            //공기청정기 위치 전까지
            if (idx == 0) {
                while (ny < curr.r - 1) {
                    nmap[ny + 1][nx] = map[ny][nx];
                    ny++;
                }
            } else {
                while (ny > curr.r + 1) {
                    nmap[ny - 1][nx] = map[ny][nx];
                    ny--;
                }
            }
        }
        cleanerCopy(nmap);
    }
 
    public static void spreadCopy(int[][] nmap) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                map[i][j] = nmap[i][j];
            }
        }
    }
 
    public static void cleanerCopy(int[][] nmap) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (i == 0 || i == r - 1 || j == 0 || j == c - 1 || i == cleaner_pos[0].r || i == cleaner_pos[1].r) {
                    map[i][j] = nmap[i][j];
                }
            }
        }
        map[cleaner_pos[0].r][cleaner_pos[0].c] = -1;
        map[cleaner_pos[1].r][cleaner_pos[1].c] = -1;
    }
 
    public static void getAns() {
        int ans = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] <= 0continue;
                ans += map[i][j];
            }
        }
        System.out.println(ans);
    }
 
    public static class Cleaner {
        int r, c;
 
        public Cleaner(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}
cs


반응형
반응형

* Review

2019 상반기 공채 오전반 복원문제중 2번문제였다.

기본 삼성유형으로 알려진 BFS, DFS에서 그냥 구현문제가 나올줄은 몰랏지만

쉬웠다는 평이 많은 상반기 코테에서 1솔로 가능할지 의문이다.

* 핵심 개념

이 문제에서는 주의할 점이 두가지 있다.

1. 물고기들 각각을 움직일 때 바로 움직이지 않고, 한번에 움직여야 한다.

필자는 Fish 배열을 만들어 정보를 저장하고 상어 움직임이 끝낫을 때 한번에 이동했다.

물론, 조건에 따라 해당 좌표에 자신보다 작은 상어가 있다면 Fish 배열에 null로 바꿔주면 된다.

2. 시간 속도를 줄이려면 움직여야 하는 거리 % (Width or Depth * 2 - 2) 계산을 하고 움직이면 된다.(584ms -> 308ms)

아쉽게도 시험장에서 30분을 고민하다 이 공식을 못찾았다.

이 두가지 조건만 만족하면 어렵지 않게 풀수있는 기출문제다.

* 문제

문제

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

낚시왕은 가장 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

  1. 낚시왕이 오른쪽으로 한 칸 이동한다.
  2. 낚시왕이 있는 열에 있는 상어 중에서 가장 땅과 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
  3. 상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계인 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 오른쪽 위에 상어를 구분하기 위해 문자를 적어 놓았다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

입력

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

출력

낚시왕이 잡은 상어 크기의 합을 출력한다.

* 소스 코드

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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dy = {-1100};
    public static int[] dx = {001-1};
    public static int width, depth, n, ans = 0;
    public static Fish[] fishInfo = new Fish[10001];
    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());
        depth = Integer.parseInt(stk.nextToken());
        width = Integer.parseInt(stk.nextToken());
        n = Integer.parseInt(stk.nextToken());
        map = new int[depth + 1][width + 1];
        for (int i = 1; i <= n; i++) {
            stk = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(stk.nextToken());
            int c = Integer.parseInt(stk.nextToken());
            int s = Integer.parseInt(stk.nextToken());
            int d = Integer.parseInt(stk.nextToken());
            int z = Integer.parseInt(stk.nextToken());
            fishInfo[z] = new Fish(z, c, r, d - 1, s);
            map[r][c] = z;
        }
        for (int i = 1; i <= width; i++) {
            //작살로 물고기 잡음
            for (int j = 1; j <= depth; j++) {
                if (map[j][i] != 0) {
                    fishInfo[map[j][i]] = null;
                    ans += map[j][i];
                    map[j][i] = 0;
                    break;
                }
            }
            //물고기 이동
            for (int j = 1; j <= 10000; j++) {
                if (fishInfo[j] == nullcontinue;
                Fish curr = fishInfo[j];
                int nx = curr.x;
                int ny = curr.y;
                int move = curr.speed;
                int d = curr.d;
                map[ny][nx] = 0;
                switch (d) {    //방향따라 case 다르게
                    //상하
                    case 0:
                    case 1:
                        move %= (depth * 2 - 2);
                        while (move > 0) {
                            if (ny == 1) {
                                d = 1;
                            }
                            if (ny == depth) {
                                d = 0;
                            }
                            ny += dy[d];
                            move--;
                        }
                        fishInfo[curr.idx] = new Fish(curr.idx, nx, ny, d, curr.speed);
                        break;
                    //좌우
                    case 2:
                    case 3:
                        move %= (width * 2 - 2);
                        while (move > 0) {
                            if (nx == 1) d = 2;
                            if (nx == width) d = 3;
                            nx += dx[d];
                            move--;
                        }
                        fishInfo[curr.idx] = new Fish(curr.idx, nx, ny, d, curr.speed);
                        break;
                }
            }
            for (int j = 1; j <= 10000; j++) {
                if (fishInfo[j] == nullcontinue;
                Fish curr = fishInfo[j];
                if (map[curr.y][curr.x] < curr.idx) {   //맵에 저장된 물고기보다 본인이 더 크면
                    fishInfo[map[curr.y][curr.x]] = null;
                    map[curr.y][curr.x] = curr.idx;
                }
            }
        }
        System.out.println(ans);
    }
 
    public static class Fish {
        int idx, x, y, d, speed;
 
        public Fish(int idx, int x, int y, int d, int speed) {
            this.idx = idx;
            this.x = x;
            this.y = y;
            this.d = d;
            this.speed = speed;
        }
    }
}
cs


반응형
반응형

* 핵심

문제를 하루종일 삽질하면서 풀었다.

첫번째 실수는 문제를 이해를 잘못해서 각 미로를 nCr로 조합한다는 경우를 생각하지 못했고, 

두번째 실수는 visited를 매번 초기화하지 않아서 한바퀴밖에 돌지않는 경우가 발생했다.


문제를 뜯어보면 3가지 역할로 분리할 수 있다.

1. nCr 함수 : 판을 쌓는 순서를 참가자가 자유롭게 정할 수 있으므로 5!의 경우의 수가 발생

2. Rotation(DFS) 함수 : 판을 돌리는 경우의 수는 총 4가지이므로 4^5(판의 개수) 의 경우의 수 발생 >> DFS로 경우의 수 찾기

3. BFS 함수 : Rotaion으로 받은 map을 가지고 0,0,0에서 4,4,4로 가는 경우의 수를 찾는 함수

문제를 위처럼 3단계로 나누고 실수없이 구현하면 금방 풀 수 있는 문제였다.

특히, 자바는 파라미터가 Call by Reference이기 때문에 DFS 함수를 호출하고 다시 값을 변경해주는 것 또한 잊지말아야 한다.


* 문제

문제

평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.

대회의 규칙은 아래와 같다.

  • 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.

  • 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.

  • 회전을 완료한 후 참가자는 판 5개를 쌓는다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로이다. 이 때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.

  • 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
  • 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.

이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자. 

입력

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.

출력

첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[][][] map = new int[5][5][5];
    public static boolean[][][] visited = new boolean[5][5][5];
    public static int[] p = {00000};        //nCr로 순서를 정할 때 idx를 저장하는 배열
    public static int[] dx = {1-10000};
    public static int[] dy = {001-100};
    public static int[] dh = {00001-1};
    public static int ans = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 5; i++) {                //높이
            for (int j = 0; j < 5; j++) {            //가로
                stk = new StringTokenizer(br.readLine());
                for (int k = 0; k < 5; k++) {        //세로
                    map[i][j][k] = Integer.parseInt(stk.nextToken());
                }
            }
        }
        nCr(0new boolean[5]);
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
 
    //참가자가 5개의 판을 쌓는 5!의 경우의 수
    public static void nCr(int cnt, boolean[] visited) {
        if (cnt == 5) {        //경우의 수를 찾았을때마다 만든 배열을 가지고 Backtracking 함수 호출
            int[][][] nmap = new int[5][5][5];
            for (int i = 0; i < 5; i++) {
                int idx = p[i];
                for (int x = 0; x < 5; x++) {
                    for (int y = 0; y < 5; y++) {
                        nmap[i][x][y] = map[idx][x][y];
                    }
                }
            }
            Backtracking(0new int[5][5][5], nmap);
            return;
        }
        for (int i = 0; i < 5; i++) {
            if (!visited[i]) {
                visited[i] = true;
                p[i] = cnt;
                nCr(cnt + 1, visited);
                p[i] = 0;
                visited[i] = false;
            }
        }
        return;
    }
 
    //dfs를 이용하여 각 높이별 회전할 때의 저장배열
    public static void Backtracking(int height, int[][][] nmap, int[][][] map) {
        if (height == 5) {        //배치한 판을 회전시킨 경우의 수마다 bfs 
            if (nmap[0][0][0== 1 && nmap[4][4][4== 1) {
                int tmp = bfs(nmap);
                if (tmp != -1) ans = Math.min(ans, tmp);
            }
            return;
        }
        for (int cnt = 1; cnt <= 4; cnt++) {     //반시계 돌리는 횟수
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (map[height][i][j] == 1) {
                        switch (cnt) {
                            case 1:
                                nmap[height][j][4 - i] = 1;
                                break;
                            case 2:
                                nmap[height][4 - i][4 - j] = 1;
                                break;
                            case 3:
                                nmap[height][4 - j][i] = 1;
                                break;
                            case 4:
                                nmap[height][i][j] = 1;
                                break;
                        }
                    }
                }
            }
            Backtracking(height + 1, nmap, map);
            nmap[height] = new int[5][5];
        }
        return;
    }
 
    //bfs를 이용해서 저장된 nmap을 가지고 정점가능횟수 찾는 횟수
    public static int bfs(int[][][] nmap) {
        Queue<Point> q = new LinkedList<>();
        visited = new boolean[5][5][5];
        q.add(new Point(0000));
        while (!q.isEmpty()) {
            Point p = q.poll();
            if (p.height == 4 && p.x == 4 && p.y == 4return p.cnt;
            if (!visited[p.height][p.x][p.y]) {
                visited[p.height][p.x][p.y] = true;
                for (int k = 0; k < 6; k++) {
                    int nh = p.height + dh[k];
                    int nx = p.x + dx[k];
                    int ny = p.y + dy[k];
                    if (check(nh, nx, ny) && nmap[nh][nx][ny] == 1 && !visited[nh][nx][ny]) {
                        q.add(new Point(nh, nx, ny, p.cnt + 1));
                    }
                }
            }
        }
        return -1;
    }
 
    public static boolean check(int h, int x, int y) {
        if (h >= 0 && h < 5 && x >= 0 && x < 5 && y >= 0 && y < 5return true;
        return false;
    }
 
    public static class Point {
        int height, x, y, cnt;
 
        public Point(int height, int x, int y, int cnt) {
            this.height = height;
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}
cs


반응형