[프로그래머스 C++] 무인도 여행

 

[프로그래머스 C++] 무인도 여행

 

https://school.programmers.co.kr/learn/courses/30/lessons/154540

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

 

해결전략

 

너비 우선 탐색, BFS

 

< 핵심전략 >

while(!Q.emtpy()) 가 돌기 전에 방문 체크 if (maps[y][x] != 'X' && ch[y][x] == 0) 를 먼저하여

다음 사이클에서 체크하지 않도록 한다. 

---

 

정답 코드

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };
 
queue<pair<int, int>> Q;
int ch[101][101];
 
vector<int> solution(vector<string> maps) {
    vector<int> answer;
 
    for (int y = 0; y < maps.size(); y++) {
        for (int x = 0; x < maps[0].size(); x++) 
        {
            int cnt = 0; // 방문지점들의 숫자를 더해주는 변수
            if (maps[y][x] != 'X' && ch[y][x] == 0) 
            {
                Q.push({ y, x }); // 방문지점 Q에 삽입
                ch[y][x] = 1;            // 방문 체크
                cnt += maps[y][x] - '0'; // 방문지점 숫자 더하기
 
                while (!Q.empty())
                {
                    int y = Q.front().first;
                    int x = Q.front().second;
                    Q.pop();
 
                    for (int i = 0; i < 4; i++)
                    {
                        int ny = y + dirY[i];
                        int nx = x + dirX[i];
 
                        if (ny < 0 || maps.size() <= ny || nx < 0 || maps[0].size() <= nx) continue;
 
                        if (maps[ny][nx] != 'X' && ch[ny][nx] == 0)
                        {
                            Q.push({ ny, nx }); // 새로운 위치 넣기
                            ch[ny][nx] = 1;            // 방문 체크
                            cnt += maps[ny][nx] - '0'; // 방문지점 숫자 더하기
                        }
                    }
                }
                answer.push_back(cnt); // 방문한 그룹의 숫자 합을 answer에 넣음
            }
        }
    }
    
 
    if (answer.empty()) 
        return vector<int>{-1};
 
	sort(answer.begin(), answer.end());
 
    return answer;
}

 

 

---