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

문제

 

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

프로그래머스

 

문제풀이

 

DFS를 이용하면 쉽게 풀 수 있는 문제이다.

2차원 bool형 벡터 visited를 이용하여 'X'인 곳을 모두 true로 바꾼다.

 

int max_day;

void DFS(int y, int x) {
    for (int idx = 0; idx < 4; ++idx) {
        int ny = y + dy[idx];
        int nx = x + dx[idx];
        if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
        if (visited[ny][nx] == true) continue;
        visited[ny][nx] = true;
        max_day += maps[ny][nx] - '0';
        DFS(ny, nx);
    }
}

DFS함수는 y, x를 인자로 받는다.

현재 위치를 기준으로 네 방향을 모두 탐색한다.

만약 범위를 벗어나거나 이미 방문한 적이 있다면 넘긴다.

처음 방문한 곳이라면 방문 표시를 한 뒤 전역 변수인 max_day에 머물 수 있는 날짜를 더한다.

 

 

    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < M; ++x) {
            if (visited[y][x] == false) {
                visited[y][x] = true;
                max_day = maps[y][x] - '0';
                DFS(y, x);
                answer.push_back(max_day);
            }
        }
    }

메인문이다.

방문을 한 적이 없는 섬을 방문표시를 하고 max_day를 해당 섬의 머물 수 있는 날짜로 초기화한다.

DFS함수가 종료되면 answer에 입력한다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector<vector<bool>>visited;
vector<string>maps;
vector<int> answer;
int N, M, max_day;

void DFS(int y, int x) {
    for (int idx = 0; idx < 4; ++idx) {
        int ny = y + dy[idx];
        int nx = x + dx[idx];
        if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
        if (visited[ny][nx] == true) continue;
        visited[ny][nx] = true;
        max_day += maps[ny][nx] - '0';
        DFS(ny, nx);
    }
}

vector<int> solution(vector<string> maps) {
    ::maps = maps;
    N = maps.size();
    M = maps[0].size();
    
    visited = vector<vector<bool>>(N, vector<bool>(M, false));
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < M; ++x) {
            if (maps[y][x] == 'X') visited[y][x] = true;
        }
    }

    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < M; ++x) {
            if (visited[y][x] == false) {
                visited[y][x] = true;
                max_day = maps[y][x] - '0';
                DFS(y, x);
                answer.push_back(max_day);
            }
        }
    }
    if (answer.empty()) answer.push_back(-1);
    else sort(answer.begin(), answer.end());

    return answer;
}