백준 14397번 - 해변 (C++)

유형: 그래프, 완탐

문제: https://www.acmicpc.net/problem/14397

14397번: 해변

 

풀이

문제에 주어진 문자열을 물이면 1, 땅이면 0인 2차원 벡터로 변환했다.

육각형 형태라, 한 노드의 주변 노드까지 합치면 꽃모양이 된다. (주변 노드는 최대 6개이기에)

2차원 벡터의 모든 노드를 탐색하면서, 땅일 경우에만 주변 노드중 바다인 것만 세주면 된다.

 

주의할 점은, 노드가 세로 몇째 줄이냐에 따라 주변 노드가 달라진다는거다.

그렇기에 짝수번째, 홀수번째 노드의 주변 노드 위치를 각각 파악해둬야 한다.

처음에 예시 그림을 보고 홀수번째 노드의 경우로만 주변을 파악했다가 틀렸었다.

 

그래프 문제중에 제일 초반에 나오고 푼 사람이 몇명 없어서 쉬워보이는데 (DFS, BFS도 필요없고)

그래도 중요한 문제인 것 같다. 왜 틀렸는지 파악하느라 조금 시간걸렸다.

#include "iostream"
#include "vector"

using namespace std;

int solution(int n, int m, vector<vector<int>> maps){
    int cnt = 0;

    int posX[] = {-1, -1, 0, 0, 1, 1};
    int posY_odd[] = {0, 1, -1, 1, 0, 1}; // 세로가 홀수번째일 때 주변
    int posY_even[] = {-1, 0, -1, 1, -1, 0}; // 세로가 짝수번째일 때 주변

    // 노드중에 땅일 때에만 주변 노드 확인
    for(int x = 0; x < n; x++){
        for(int y = 0; y < m; y++){

            if(maps[x][y]) continue; // 바다면 넘김

            // 주변 노드 확인
            for(int i = 0; i < 6; i++){
                int tempX = x + posX[i], tempY;
                if(x % 2 == 0) tempY = y + posY_even[i];
                else tempY = y + posY_odd[i];

                // 범위에 해당하는것만 카운트
                if(-1 < tempX && tempX < n && -1 < tempY && tempY < m){
                    if(maps[tempX][tempY]) cnt ++;
                }
            } // 주변 노드 확인 끝
        }
    }

    return cnt;
}

int main(){

    int n, m; cin >> n >> m;
    vector<vector<int>> maps(n);

    for(int i = 0; i < n; i++){
        string temp; cin >> temp;
        for(auto now: temp){
            if(now == '.') maps[i].push_back(1);
            else maps[i].push_back(0);
        }
    }

    cout << solution(n, m, maps) << endl;

    return 0;
}