반응형
BFS ...,,,,, 비트 마스크 .,,.,..
이거 어떻게 풀지 몰라서 다른 사람들 코드를 보고 이해한 후 풀었다.
비트마스크가 이렇게 쓰일 수 있다는 것이 너무 신기했다.
풀이
1. BFS를 통해 탐색을 하면 된다.
2. 키의 개수가 a~f 까지, 6개이다. N과 M의 최대값은 50, 2^6은 64이므로 최대 50x50x64 이므로 배열을 만들어서 관리해도 크게 상관없다.
3. 해당위치에 어떤 키를 갖고 방문했는지 판단을 하여 재 방문 하지 않게 한다. 이때 비트마스크를 사용한다.
비트마스크를 이용한 키를 이용하는 방법은 2진수를 생각하면 된다.
키는 총 6개 비트는 6개를 사용한다. << , >> 이용한 shift 연산을 하면 해당 비트를 출력또는 변경 시킬 수 있다.
예를들어)
a키를 갖고 있을 경우는 100000 가 되고
a,b키를 갖고 있는 경우에는 110000
a,b,c키를 갖고 있는 경우 111000
모든 키를 갖고 있는경우는 111111이 된다.
이러한 비트마스크를 이용하여 문제를 풀어보자.
(1,1)에 a키를 갖고 방문했을 때는 Boolean check[1][1][0]에 접근하여 true로 값을 바꾼다.
이후 a키만 갖고 있을때는 Check[][][] 함수를 통해 (1,1)은 방문하지 않는다.
하지만 b키 또는 다른 키들을 획득한 후 (1,1)에 방문할 경우 Boolean check[1][1][1~64] 사이의 값을 접근하는 것이므로 (1,1)에 방문 할 수 있다.
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 104 105 106 107 108 109 110 111 | import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; public class Main { static int N; static int M; static char[][] arr; static boolean[][][] check; static int[] dx = { 1, -1, 0, 0 }; static int[] dy = { 0, 0, 1, -1 }; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"))); // BufferedReader br = new BufferedReader(new // InputStreamReader(System.in)); int Testcase = Integer.parseInt(br.readLine()); for (int t = 1; t <= Testcase; t++) { String[] str = br.readLine().split(" "); N = Integer.parseInt(str[0]); M = Integer.parseInt(str[1]); Dot start = null; arr = new char[N][M]; check = new boolean[N][M][1 << 6]; for (int i = 0; i < N; i++) { str = br.readLine().split(""); for (int j = 0; j < M; j++) { arr[i][j] = str[j].charAt(0); if (arr[i][j] == '0') { start = new Dot(i, j, 0); } } } System.out.print("#" + t + " "); System.out.println(BFS(start)); } } public static int BFS(Dot start) { Queue<Dot> q = new LinkedList<Dot>(); q.add(start); check[q.peek().x][q.peek().y][0] = true; int Hour = 0; while (!q.isEmpty()) { int size = q.size(); for (int qsize = 0; qsize < size; qsize++) { Dot d = q.poll(); int currentX = d.x; int currentY = d.y; int currentKey = d.key; System.out.println(currentX + " " + currentY); if (arr[currentX][currentY] == '1') { return Hour; } for (int i = 0; i < 4; i++) { int nextX = currentX + dx[i]; int nextY = currentY + dy[i]; int key = currentKey; //범위 밖이면 통과 if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) { continue; } // 벽을 만나면 통과 if (arr[nextX][nextY] == '#') { continue; } //a 와 f 사이 키 일때 해당 위치의 값을 1로 만들어준다. if ('a' <= arr[nextX][nextY] && arr[nextX][nextY] <= 'f') { key |= (1 << arr[nextX][nextY] - 'a'); } //A 와 F 사이 키를 갖고 있는지 확인한 후 없다면 패스한다. if ('A' <= arr[nextX][nextY] && arr[nextX][nextY] <= 'F') { if ((key & (1 << (arr[nextX][nextY] - 'A'))) == 0) { continue; } } //해당 위치에 똑같은 키들을 갖고 방문했다면 패스 if (check[nextX][nextY][key]) { continue; } //해당 위치에 똑같은 키들을 갖고 방문한 적 없으면 방문 후, 재 방문 금지하기 위한 조건걸어둠. check[nextX][nextY][key] = true; q.add(new Dot(nextX, nextY, key)); } } Hour++; } return -1; } } class Dot { int x; int y; int key; Dot(int x, int y, int key) { this.x = x; this.y = y; this.key = key; } } | cs |
반응형
'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글
| [BOJ] 백준 2798 - 블랙잭 (자바) (0) | 2018.05.04 |
|---|---|
| [BOJ] 백준 2579 - 계단 오르기 (자바) (0) | 2018.05.03 |
| [BOJ] 백준 1003 - 피보나치 함수 (자바) (0) | 2018.04.30 |
| [BOJ] 백준 11720 - 숫자의 합 (자바) (0) | 2018.04.26 |
| [BOJ] 백준 15686 - 치킨 배달 (자바) (0) | 2018.04.16 |