[백준 1194] 달이 차오른다, 가자. (C++)

A. 문제설명

www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

문제에 대한 자세한 설명은 링크 참조

 

1. N*M 미로가 존재

2. 해당 미로의 각 엔트리에는 다음과 같은 규칙이 적용됨

빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
벽 : 절대 이동할 수 없다. (‘#’)
열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

3. 여기서 미로를 탈출하기 위해 최소로 이동하는 경우를 구하라.

 

B. 접근법

BFS + 비트연산

 

간단한 BFS 미로 탐색문제이다. 그러나 이번에는 열쇠와 문이라는 특별한 조건이 달려있다. 각 열쇠는 문자 a-f에 해당하는데 각 문들은 이에 해당하는 A-F의 값을 가진다. 각 문에 대응되는 열쇠를 가진 경우에만 해당 경로를 지날 수 있다.

여기서, 열쇠/문 조합의 갯수는 6개이기 때문에 조합을 구하면 2^6=64가지가 된다. 즉 크지 않은 값이기 때문에 이 문제에서는 해당 열쇠를 가진 상태를 탐사시 확인해주어야 한다. 

 

나의 경우 char_to_bit()/bit_check() 두 함수를 이용하여 각 큐의 엔트리에서 열쇠를 들고있는 지 여부와 해당 경로에서 열쇠를 들고 있었을 때 반복탐색을 하지 않도록 체크해주었다.(bool visit[50][50][64] = {0, }; // N*M*2^KEY)

int char_to_bit(char c){ return pow(2,c-'a'); }
bool bit_check(int b, char c){
  // b:kBit 입력, c:확인하고자 하는 key(소문자), 가지고 있으면 true 반환
  bool bArr[6];
  int num = 32;
  for (int i = 0; i < 6; i++) {
    bArr[i] = (b/num);
    b%=num;
    num/=2;
  }
  return bArr[5-(int)(c-'a')];
}

 

C. 풀이

1. 0의 위치에서 BFS 탐사 시작

2. 다음 위치가 .인 경우: 그대로 진행

3. 다음 위치가 a-f인 경우: bit count하고 구조체에 추가하고 push

4. 다음 위치가 A-F인 경우: 현재 구조체에서 bit 계산시 있으면 push

5. 다음 위치가 1인 경우: +1 return

 

D. 내 코드