728x90
728x90
https://www.acmicpc.net/problem/21736
풀이
전형적인 BFS문제
- 도연(I)는 한 번만 주어짐이 보장됨으로 입력시에 도연 위치 좌표 저장
- 도연 위치 좌표부터 BFS를 실행해서 상,하,좌,우 움직이면서 조건에 맞는 좌표 저장
- P 만날때마다 +1
#include <bits/stdc++.h>
using namespace std;
int visited[601][601] = { 0, };
char campus[601][601] = { 0, };
int people = 0;
int num1, num2; // num1 == x축 , num2 == y축
int bfs(int x, int y) {
queue<pair<int, int>> qu;
qu.push({ x,y});
visited[x][y] = 1;
while (!qu.empty()) {
int cur_x = qu.front().first;
int cur_y = qu.front().second;
qu.pop();
if (campus[cur_x][cur_y] == 'P') {
people++;
}
if (cur_y - 1 > -1 && visited[cur_x][cur_y - 1] == 0 && campus[cur_x][cur_y - 1] != 'X') { // 왼쪽으로 갈 수 있는 경우
visited[cur_x][cur_y - 1] = 1;
qu.push({ cur_x,cur_y - 1 });
}
if (cur_y + 1 < num2 && visited[cur_x][cur_y + 1] == 0 && campus[cur_x][cur_y + 1] != 'X') { // 오른쪽으로 갈 수 있는 경우
visited[cur_x][cur_y + 1] = 1;
qu.push({ cur_x,cur_y + 1 });
}
if (cur_x + 1 <num1 && visited[cur_x+1][cur_y] == 0 && campus[cur_x+1][cur_y] != 'X') { //아래쪽으로 갈 수 있는 경우
visited[cur_x+1][cur_y] = 1;
qu.push({ cur_x+1,cur_y });
}
if (cur_x -1 >-1 && visited[cur_x - 1][cur_y] == 0 && campus[cur_x - 1][cur_y] != 'X') { //위쪽으로 갈 수 있는 경우
visited[cur_x - 1][cur_y] = 1;
qu.push({ cur_x - 1,cur_y });
}
}
return people;
}
int main(){
int x, y;
cin >> num1 >> num2;
for (int i = 0; i < num1; i++) {
string tmp;
cin >> tmp;
for (int j = 0; j < tmp.size(); j++) {
campus[i][j] = tmp[j];
if (tmp[j] == 'I') {
x = i;
y = j;
}
}
}
int ans = bfs(x, y);
if (ans == 0) {
cout << "TT" << endl;
}
else {
cout << ans << endl;
}
}
BFS풀때마다 다들 간결하게 짜던데 내 if문은 왜이렇게 더러운지,,, 다른 사람들 풀이보고 내 것으로 만드는 연습을 하자....!
728x90
728x90
'Algorihtm > BOJ' 카테고리의 다른 글
C++ 백준 2847번 : 게임을 만든 동준이 (0) | 2023.08.04 |
---|---|
C++ 백준 2667번 : 단지번호붙이기 (0) | 2023.07.06 |
C++ 백준 13164번 : 행복유치원 (0) | 2023.06.23 |
C++ 백준 1992번 : 쿼드트리 (0) | 2023.05.29 |
C++ 백준 21921번 : 블로그 (0) | 2023.05.24 |