백준) 2615 오목

오목

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

오목판이 주어지고 현재 누가 이겼는지를 판별해야한다.

모든 알을 보고 최대한 빨리 판별해보자.

오목에서 승리란 알을 연속으로 5개 두어야 생긴다. 방향은 가로, 세로, 대각선이 가능하다.

왼쪽 위부터 오른쪽으로, 아래로 모든 알을 본다면, 네 가지 방향으로 연속적인지만 판별하면 된다.

1. 아래 2. 오른쪽 3. 우하 대각선 4.우상 대각선

6개 두면 이긴게 아니기 때문에, 기존에 6개를 카운트 한 것을 방향 때문에 5개로 착각할 수 있다.

따라서 5개로 착각하지 않게 하기 위해, 정반대 방향의 돌을 하나 봐서, 현재 보는 돌이 시작점인지 확인할 수 있다.

visit으로 체크하는 방법은, 오목이 돌이 여러 방향들에 걸쳐진다는 점에서 쓸 수 없다.

#include <stdio.h>
 
int map[19][19];
int dir[4][2] = { {1,0},{1,1},{0,1},{-1,1} };
 
bool is_in_range(int y, int x) {
    return (y >= 0 && x >= 0 && y < 19 && x < 19);
}
 
int getMap(int y, int x) {
    if (y < 0 || x < 0 || y >= 19 || x >= 19)
        return 0;
    return map[y][x];
}
 
int main() {
    for (int i = 0; i < 19; ++i)
        for (int j = 0; j < 19; ++j)
            scanf("%d", &map[i][j]);
 
    int ans_y = -1, ans_x = -1, ans_c = -1;
 
    for (int d = 0; d < 4; ++d) {
        for (int x = 0; x < 19; ++x) {
            for (int y = 0; y < 19; ++y) {
                if (map[y][x] == 0)
                    continue;
 
                if (getMap(y - dir[d][0], x - dir[d][1]) == map[y][x])
                    continue;
 
                int yy = y, xx = x, cnt = 0;
                while (1) {
                    yy += dir[d][0];
                    xx += dir[d][1];
 
                    if (!is_in_range(yy, xx))
                        break;
 
                    if (map[yy][xx] != map[y][x])
                        break;
 
                    cnt++;
                }
                if (cnt == 4) {
                    ans_y = y;
                    ans_x = x;
                    ans_c = map[y][x];
                }
            }
        }
    }
 
    if (ans_c == -1) {
        printf("0");
        return 0;
    }
 
    printf("%d\n%d %d", ans_c, ans_y + 1, ans_x + 1);
    return 0;
}