[BOJ] 21736 헌내기는 친구가 필요해

https://www.acmicpc.net/problem/21736

21736번: 헌내기는 친구가 필요해

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

bfs / dfs

 

---------------------------------------------------풀이----------------------------------------------------

 

최단 거리를 찾는 것이 아니므로 dfs, bfs 등 어떤 탐색 알고리즘을 사용해도 무관하지만,

bfs가 편해서 이용하였다.

시작점인 I의 위치를 pair start에 저장하고,

solution() 함수에서 queue의 front를 꺼내올 때마다 사람인지('P'인지) 체크해 수를 세서 리턴하였다.

visited[][]를 선언해 한 번 방문한 위치는 다시 방문하지 않도록 하였다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int N, M;
char map[601][601] = {0, };
bool visited[601][601] = {false, };
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
pair<int,int> start;

int solution(){
    int ret = 0;
    pair<int,int> cur;
    cur = start;
    queue<pair<int,int> > q;
    q.push(cur);
    visited[cur.first][cur.second] = true;
    while(!q.empty()){
        cur = q.front();
        q.pop();
        if(map[cur.first][cur.second] == 'P'){
            ret++;
        }
        for(int i = 0; i < 4; i++){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= M 
                || visited[nx][ny] || map[nx][ny] == 'X'){
                continue;
            }
            q.push(make_pair(nx, ny));
            visited[nx][ny] = true;
        }
    }
    return ret;
}

int main(void){
    FASTIO;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> map[i][j];
            if(map[i][j] == 'I'){
                start.first = i; start.second = j;
            }
        }
    }
    int ans = solution();
    if(ans == 0){
        cout << "TT\n";
    }
    else{
        cout << ans << "\n";
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

간단한 그래프 탐색