[C++] 무인도 여행

[문제]

코딩테스트 연습 - 무인도 여행 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

bfs를 이용하면 쉽게 해결이 되는 문제.

이중 반복문을 통해 maps를 돌면서 만약 벽이 아니면서 동시에 이전에 방문을 해보지 않았다면 해당 지점부터 bfs를 해주자.

[회고]

특별히 어려운 점은 없었다. 레벨2에 딱 맞았던 문제인데 예전이었으면 몇번 헤맸을 수도 있었을 것 같다. 실력 향상이 느껴져서 기분이 좋음ㅎㅎ

[코드]

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

int visited[101][101];
int n, m;

int bfs(int i, int j, vector<string> maps){
    int answer = 0;
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    
    queue<pair<int,int> > q;
    q.push(make_pair(i,j));
    answer += maps[i][j] - '0';
    visited[i][j] = 1;    
    
    while(q.size() > 0){
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();
        for(int k = 0;k<4;k++){
            int nextX = curX + dx[k];
            int nextY = curY + dy[k];
            if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= m){
                continue;
            }
            if(maps[nextX][nextY] == 'X'){
                continue;
            }
            if(visited[nextX][nextY] == 1){
                continue;
            }
            visited[nextX][nextY] = 1;
            answer += maps[nextX][nextY] - '0';
            q.push(make_pair(nextX,nextY));
        }
    }
    return answer;
}

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    n = maps.size();
    m = maps[0].size();
    
    for(int i = 0;i<maps.size();i++){
        for(int j = 0;j<maps[i].size();j++){
            if(visited[i][j] == 0 && maps[i][j] != 'X'){
                answer.push_back(bfs(i,j,maps));
            }
        }
    }
    if(answer.size() == 0) answer.push_back(-1);
    sort(answer.begin(),answer.end());
    return answer;
}