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

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

14397번: 해변

---

Level: Silver IV

Solved By: Graph

 

육각형이기 때문에 행에 따라 인접할 수 있는 블록의 위치를 구현할 수 있다면 그래프 탐색으로 쉽게 풀 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>
#define MAX 51
using namespace std;

int N, M;
char m[MAX][MAX];
bool visited[MAX][MAX];

struct dir{
    int y, x;
};

dir dir_odd[6] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, -1}};
dir dir_even[6] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, 1}, {1, 1}};

int bfs(int row, int col){
    int ret = 0;
    
    queue<pii> q;
    q.push({row, col});
    visited[row][col] = true;
    
    while(!q.empty()){
        int ny = q.front().first;
        int nx = q.front().second;
        
        q.pop();
        
        for(int i = 0; i < 6; i++){
            int dy, dx;
            if(ny % 2){
                dy = ny + dir_odd[i].y;
                dx = nx + dir_odd[i].x;
            }
            else{
                dy = ny + dir_even[i].y;
                dx = nx + dir_even[i].x;
            }
            
            if(dy > N || dy < 1 || dx > M || dx < 1) continue;
            if(visited[dy][dx]) continue;
            
            if(m[dy][dx] == '#') ret++;
            else{
                q.push({dy, dx});
                visited[dy][dx] = true;
            }
        }
    }
    return ret;
}

int main(){
    cin >> N >> M;
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> m[i][j];
        }
    }
    
    int res = 0;
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(visited[i][j]) continue;
            else if(m[i][j] == '#') continue;
            res += bfs(i, j);
        }
    }
    
    cout << res;
    return 0;
}