[백준/C++] 16955번 오목, 이길 수 있을까?

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

16955번: 오목, 이길 수 있을까?

문제분석

누구나 쉽게 알 수 있는 오목게임이다.

구사과와 큐브러버는 10x10크기의 바둑판에서 오목을 하고 있다.

턴은 구사과가 먼저 갖는데, 바둑판의 상태가 입력으로 주어지고 구사과가 턴을 한 번 더 가졌을 때,

즉, 한 수를 두었을 때 이길 수 있는지 구하는 프로그램을 작성해아한다.

오목의 승리 룰은 가로,세로 대각선 방향 중 하나에서 자신의 돌이 5개 이상 연속하는 것이다.

만약 구사과가 승리할 수 있으면 1, 아니면 0을 출력한다.

코드

#include<iostream>

using namespace std;

int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 }; // 방향 벡터
// -1, -1 = 대각선 좌상 | -1, 1 = 대각선 좌하 | 1, -1 = 대각선 우상 | 1, 1 = 대각선 우하
// -1, 0 = 왼쪽으로 진행하는 가로 | 1, 0 = 오른쪽으로 진행하는 가로 
// 0, -1 = 위로 상승하는 세로 | 0, 1 = 아래로 내려가는 세로
char board[10][10];

int check(int x, int y) {
	for (int i = 0; i < 8; i++) {

		int cx = x; // 현재 위치를 받음
		int cy = y;

		int cnt = 1;
		int empty = 0;

		for (int j = 0; j < 4; j++) {
			int current_x = cx + dx[i]; // 방향 이동
			int current_y = cy + dy[i];

			if (0 <= current_x && current_x < 10 && 0 <= current_y && current_y < 10) {
				if (board[current_x][current_y] == 'X') {
					cnt++;
				}
				if (board[current_x][current_y] == '.') {
					empty++;
				}
				cx = current_x;
				cy = current_y;  //해당방향의 그 다음 돌 검색 
			}

			else {
				break;
			}
		}
		if (cnt == 4 && empty == 1)return 1; // 한 수를 두었을 때 승리가능하면 return 1

	}
	return 0;
}

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

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> board[i][j]; // 보드 입력
		}
	}
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (board[i][j] == 'X') { // X를 만났을 때
				if (check(i, j)) { // 승리 가능한지 체크
					cout << 1 << '\n';
					return 0;
				}
			}
		}
	}
	cout << 0 << '\n';

	return 0;
}

문제풀이

1. 보드를 입력받는다.

2. 보드를 탐색하며 X(구사과)를 만났을 때, check 함수를 호출한다.

3. X를 만난 현재 위치를 cx,cy 변수에 담는다.

4. X를 만나서 함수를 호출 했으므로 X의 개수를 세는 변수 cnt를 1로 설정하고,

빈곳(.)을 세는 변수 empty를 0으로 설정한다.

5. 첫번째 for문을 방향벡터의 크기 만큼 돌리고, 두번째 for문을 4번 돌린다.

(본인을 제외한 나머지 4개의 칸을 탐색하여 하나의 빈곳과 3개의 X로 이루어져야 하기 때문에 4번 돌린다.)

6. 방향벡터의 값에 따라 가로 또는 세로 또는 대각선으로 진행하면서 X의 개수와 빈곳(.)의 개수를 센다.

7. 만약 X의 개수가 4개이고 빈곳이 1개라면, 구사과가 한 수를 두었을 때 승리 가능한 경우가 성립하므로 return 한다.

​

※ 일일이 다 탐색할 수도 있지만, 방향 벡터의 사용법을 알고 있다면 쉽게 풀 수 있는 문제였다.