티스토리 뷰
1. 문제 링크
https://www.acmicpc.net/problem/1194
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.
www.acmicpc.net
2. 문제 개요
3. 문제 힌트
key를 소지한 상태를 어떻게 나타낼 것인지가 관건.
4. 문제 풀이
5. 코드
//1시간 8분 #include <stdio.h> #include <queue> using namespace std; struct COORD { int y, x; int key; int time; }; //0 -> key가 없을때.. #define KEY_NONE 0 #define KEY_A 1 #define KEY_B 2 #define KEY_C 4 #define KEY_D 8 #define KEY_E 16 #define KEY_F 32 bool visited[64][50][50] = { false, }; char map[50][50]; int r, c; const int dx[] = { 1,-1,0,0 }; const int dy[] = { 0,0,1,-1 }; int ret = -1; int main(void) { COORD start; scanf("%d %d", &r, &c); for (int i = 0; i<r; i++) for (int j = 0; j < c; j++) { scanf("%c", &map[i][j]); if (map[i][j] == '\n'){ j--; continue; } //find 민식 if (map[i][j] == '0') start.time = 0, start.y = i, start.x = j,start.key = KEY_NONE; } //start. queue<COORD> q; visited[start.key][start.y][start.x] = true; q.push(start); while (!q.empty()) { COORD cur = q.front(); q.pop(); if (map[cur.y][cur.x] == '1') { ret = cur.time; break; } for (int dir = 0; dir < 4; dir++) { COORD next; next.y = cur.y + dy[dir]; next.x = cur.x + dx[dir]; next.time = cur.time + 1; next.key = cur.key; //boundary if (next.y < 0 || next.x < 0 || next.y >= r || next.x>= c || map[next.y][next.x] == '#') continue; //don't have a key if ((next.key & KEY_A) == 0 && map[next.y][next.x] == 'A') continue; if ((next.key & KEY_B) == 0 && map[next.y][next.x] == 'B') continue; if ((next.key & KEY_C) == 0 && map[next.y][next.x] == 'C') continue; if ((next.key & KEY_D) == 0 && map[next.y][next.x] == 'D') continue; if ((next.key & KEY_E) == 0 && map[next.y][next.x] == 'E') continue; if ((next.key & KEY_F) == 0 && map[next.y][next.x] == 'F') continue; if (visited[next.key][next.y][next.x] == false) { //키가 없고, 키가 있다면, visited[next.key][next.y][next.x] = true; if ((next.key & KEY_A) == 0 && map[next.y][next.x] == 'a') next.key += KEY_A; if ((next.key & KEY_B) == 0 && map[next.y][next.x] == 'b') next.key += KEY_B; if ((next.key & KEY_C) == 0 && map[next.y][next.x] == 'c') next.key += KEY_C; if ((next.key & KEY_D) == 0 && map[next.y][next.x] == 'd') next.key += KEY_D; if ((next.key & KEY_E) == 0 && map[next.y][next.x] == 'e') next.key += KEY_E; if ((next.key & KEY_F) == 0 && map[next.y][next.x] == 'f') next.key += KEY_F; visited[next.key][next.y][next.x] = true; q.push(next); } } } printf("%d", ret); return 0; }
'알고리즘 > BFS' 카테고리의 다른 글
| boj, 백준) 5214. 환승 ( C / C++ ) (0) | 2020.03.07 |
|---|---|
| boj, 백준) 2234 성곽(C / C++) (0) | 2020.02.26 |
| BOJ, 백준) 17135 캐슬디펜스 ( C / C++) (0) | 2020.01.08 |
| [백준] 3187. 양치기 꿍 ( C / C++) (0) | 2019.12.24 |
| [백준] 6087. 레이저 통신 ( C / C++) (0) | 2019.12.24 |