[Algorithm] 백준 - 마라톤 틱택토 (3024번)

문제

[백준] 마라톤 틱택토
(Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #6)

사용 알고리즘

- 브루트 포스 (Brute Force)

해결방법

• 입력 받은 보드에서 행, 열 또는 대각선 방향에서 3연속하는 이니셜이 있는 경우 승리자로 취급한다
• 전체 좌표를 돌면서 대각선 좌측 아래 방향, 아래 방향, 대각선 우측 아래 방향, 우측 방향 이렇게 총 4가지 방향을 탐색한다

탐색 방향

• 최소 3개만 연속하면 되므로, 좌표마다 같은 방향으로 최대 2칸 까지만 탐색한다
• 범위를 벗어나는 경우 탐색하지 않는다
• 같은 이니셜이 3개 이상 연속한 경우 탐색을 완전 종료한다
• 반례 모음집

정답 : A

포인트 : 대각선 방향 탐색시 가능한 대각선은 다 봐야한다

4
....
...A
..A.
.A..


4
....
A...
.A..
..A.


5
.....
...A.
..A..
.A...
.....

 

정답 : A

포인트 : 행, 열 대각선 각각 탐색으로 구현한 경우 열 탐색이 제대로 안될 수도 ?

3
.A.
.A.
.A.

 

정답 : A

포인트 : 연속한 문자가 최소 3개 이상이면 된다 (ongoing이 출력되면 안됨)

4
....
..A.
AAA.
.B.B

 

 

소스코드

사용언어 : C++

#include <iostream>
#include <string>

using namespace std;

int N;
char board[31][31];
int dir[4][2] = {{1, -1}, {1,0}, {1,1}, {0,1}}; //대하좌, 하, 대하우, 우

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

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> board[i][j];
        }
    }

    string winner = "ongoing";

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            char ch = board[i][j];
            if (ch == '.') continue; // 빈칸인 경우 탐색 X

            for (int d=0; d<4; d++) {
                int same = 1;
                for (int f=1; f<3; f++) { // 현재 방향으로 2칸 앞까지 확인
                    int ny = i + dir[d][0]*f;
                    int nx = j + dir[d][1]*f;

                    if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue; // 범위를 벗어나는 경우
                    if (ch == board[ny][nx]) same++;
                }
                if (same >= 3){
                    winner = ch;
                    break;
                } 
            }
        }
    }

    cout << winner;

    return 0;
}

 

 

한줄평

처음엔 대각선, 행, 열 탐색을 각각의 for 문으로 구현했는데 ㅠㅠ 계속 틀렸다고 나와서 미치는 줄 알았다. 대각선 방향은 전부 탐색해야 하는걸 놓쳐서 헛다리만 잔뜩 짚은듯.;;