[백준/BOJ] 15671번 오델로 (C++)

www.acmicpc.net/problem/15671

15671번: 오델로

오델로 자체가 뭔지 일단 알아야 쉽게 풀 수 있는 구현 문제입니다. (문제만으로 이해가 잘 안가면 링크를 참조하세요!)

 

홀수번째 순서는 흑색돌, 짝수번째 순서는 백색돌을 둔다고 설정합니다. 미리 8방향 배열을 만들고, 현재 돌은 두는 위치를 하나 정합니다. 어떤 돌을 바꿀 수 있나 탐색을 시작하는데 '.'을 만나거나, map 범위를 벗어나거나, 이미 방문한 경우는 돌의 색을 바꿀 수 없음을 의미합니다. 이외의 경우 본인의 색깔을 만나기 전까지 계속 방문 배열을 true 처리해줍니다. 체크가 끝나고 돌을 바꿀 수 있던 경우에만 방문했던 모든 부분의 색을 같게 만들어줍니다. (true로 기록되어있음)

이와 같은 과정을 반복하고, 마지막에 map의 모습과 어떤 돌을 더 많이 썼는지 출력하면 됩니다. 

 

#include <iostream>
#include <cstring>
using namespace std;

int n, m;
char map[7][7];
bool visit[7][7];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

// 돌 색 바꾸기 (흑색인지 백색인지) 
void change(int type) {
    for(int i = 1; i <= 6; i++) {
        for(int j = 1; j <= 6; j++) {
            if(type % 2 == 1 && visit[i][j]) map[i][j] = 'B';
            else if(type % 2 == 0 && visit[i][j]) map[i][j] = 'W';
        }
    }
}

// 어떤 돌이 바뀔건지 체크 (x/y좌표, 흑색인지 백색인지, 탐색 방향) 
bool check(int x, int y, int type, int dir) {
    bool flag = false;
    int nx = x;
    int ny = y;
    visit[nx][ny] = true;
    if(type % 2 == 1) {
        while(1) {
            nx += dx[dir];
            ny += dy[dir];
            if(nx < 0 || nx >= 7 || ny < 0 || ny >= 7) break;
            if(visit[nx][ny] || map[nx][ny] == '.') break;
            if(map[nx][ny] == 'B') {
                flag = true;
                break;
            }
            visit[nx][ny] = true;
        }
    } else {
        while(1) {
            nx += dx[dir];
            ny += dy[dir];
            if(nx < 0 || nx >= 7 || ny < 0 || ny >= 7) break;
            if(visit[nx][ny] || map[nx][ny] == '.') break;
            if(map[nx][ny] == 'W') {
                flag = true;
                break;
            }
            visit[nx][ny] = true;
        }
    }
    return flag;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;

    // 오델로 맵 초기화 
    for(int i = 1; i <= 6; i++) {
        for(int j = 1; j <= 6; j++) {
            map[i][j] = '.';
        }
    }
    map[3][3] = 'W';
    map[3][4] = 'B';
    map[4][3] = 'B';
    map[4][4] = 'W';

    // 어떤 돌을 바꿀건지 체크하고, 돌의 색을 바꾼다. 
    for(int i = 1; i <= n; i++) {
        int r, c;
        cin>>r>>c;
        for(int j = 0; j < 8; j++) {
            memset(visit, false, sizeof(visit));
            if(check(r, c, i, j)) change(i);
        }
    }

    // 최종 결과 출력 및 더 많이 남은 돌 구하기 
    int wSum = 0, bSum = 0;
    for(int i = 1; i <= 6; i++) {
        for(int j = 1; j <= 6; j++) {
            if(map[i][j] == 'W') wSum++;
            else if(map[i][j] == 'B') bSum++;
            cout<<map[i][j];
        }
        cout<<"\n";
    }

    wSum > bSum ? cout<<"White" : cout<<"Black";
}