728x90
반응형
https://www.acmicpc.net/problem/9328
9328번: 열쇠
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가
www.acmicpc.net
1. Logic
방에 들어갈 때 .이나 $이면 들어갈 수 있기 때문에 방 주변을 이동 가능한 공간으로 둘러싸서 입구를 찾아준다.
BFS함수 안에서 각 열쇠마다 키가 없을 때 방문했던 좌표를 queue에 저장해놓고 키를 찾으면 queue에서 뽑았던 좌표를 빼서 확인해준다.
아이디어가 신박했다.
2. Code
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int h, w;
char room[102][102];
bool vis[102][102];
bool key[26];
int bfs() {
queue<pair<int, int>> q;
queue<pair<int, int>> keyDir[26];
int ans = 0;
q.push({0, 0});
vis[0][0] = true;
while(!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
if(room[y][x] == '$') ans++;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx > w+1 || ny > h+1) continue;
if(room[ny][nx] == '*') continue;
if(vis[ny][nx]) continue;
if(room[ny][nx] >= 'A' && room[ny][nx] <= 'Z') {
int keyNum = room[ny][nx]-'A';
if(key[keyNum]) {
vis[ny][nx] = true;
q.push({ny, nx});
}
else {
keyDir[keyNum].push({ny, nx});
}
}
else if(room[ny][nx] >= 'a' && room[ny][nx] <= 'z') {
int keyNum = room[ny][nx]-'a';
vis[ny][nx] = true;
key[keyNum] = true;
q.push({ny, nx});
while(!keyDir[keyNum].empty()) {
q.push(keyDir[keyNum].front());
keyDir[keyNum].pop();
}
}
else {
vis[ny][nx] = true;
q.push({ny, nx});
}
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--) {
memset(room, '.', sizeof(room));
memset(vis, false, sizeof(vis));
memset(key, false, sizeof(key));
cin >> h >> w;
for(int i = 1; i <= h; i++) {
for(int j = 1; j <= w; j++) {
cin >> room[i][j];
}
}
string k;
cin >> k;
if(k != "0") {
for(int i = 0; i < k.size(); i++) {
key[k[i]-'a'] = true;
}
}
cout << bfs() << "\n";
}
}
알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐
728x90
반응형
'Algorithm > Beakjoon' 카테고리의 다른 글
[백준/Baekjoon] 2665 미로만들기 C++ :: BFS & Dijkstra (0) | 2024.01.06 |
---|---|
[백준/Baekjoon] 17070 파이프 옮기기 1 C++ :: Implementation (1) | 2024.01.05 |
[백준/Baekjoon] 11600 구간 합 구하기 C++ :: Prefix sum (2) | 2024.01.03 |
[백준/Baekjoon] 11066 파일 합치기 C++ :: Dynamic Programming (0) | 2024.01.01 |
[백준/Baekjoon] 2167 2차원 배열의 합 C++ :: Prefix sum (1) | 2024.01.01 |