[백준] 2615번 오목

문제 접근

2615번 오목 바로가기

사용 알고리즘

완전 탐색 + DFS

방향 설정

오목인지 판단을 하기 위해선 한 점에 대해서 총 8방향을 봐야한다.

하지만 2중 for문을 사용할 때, 위에서 아래 / 왼쪽에서 오른쪽으로 탐색을 하게 된다면,

파란색을 칠해진 방향에 대해선 볼 필요가 없다 (중복되기 때문)

5목 판단

DFS 시작

2중 for문을 이용하여 위에서 아래 / 왼쪽에서 오른쪽 으로 탐색을 하다가 0이 아닌 값일 경우, 이 점으로부터 DFS를 시작하면 된다.

DFS의 인자

bool dfs(int y, int x, int color, int dir, int depth);
시작 주소, color값, 방향, 깊이 (연속적으로 놓인 바둑알 수)

방문처리

위의 사진처럼 완전탐색으로 바둑알의 시작점을 찾기 때문에 해당 방향으로 탐색을 했었어도 중복해서 세는 경우가 생긴다. 이 경우를 없애주기 위해서 해당 방향으로 진행한 적이 있는지 방문처리를 해줘야 한다.

필자는 방문처리를 위해 DFS를 진행할 때마다 visited[y][x][dir] = true로 선언해주면서 방문처리를 진행하였다.

DFS 종료 (+ 오목 판단)

1. 오목판을 넘어감 (경계)
2. DFS를 처음 들어왔을 당시의 color값과 현재의 color값이 다름
3. 해당 방향으로 탐색한 적이 있는 경우

위의 조건에 걸렸을 때, depth (연속적으로 놓인 바둑알의 수)가 5인지 판단하면 된다.

좌표 출력

zero indexing 방식으로 진행했기 때문에 5목이 되었을 경우, y값과 x값에 각각 1씩 더해주어 반환을 해주었다.

주의

왼쪽 아래로 오목이 형성된 경우, 출력은 맨 왼쪽 아래의 위치를 출력해 줘야 한다. 따라서 이 경우에 한해서만 y값에는 5를 더해주고, x값에는 3을 빼주어 반환하였다.

소스코드

#include <iostream>
#define MAX 19

using namespace std;

int board[MAX][MAX];
bool v[MAX][MAX][4] = { 0, };

int dy[] = { 0, 1, 1, 1 };
int dx[] = { 1, 0, 1, -1 };

bool dfs(int y, int x, int color, int dir, int depth) {
	if (v[y][x][dir]) { // y, x에서 dir 방향으로 이동한 적이 있다 = 이 경로는 오목이 되지 못한다.
		return false;
	}

	// 오목 판의 경계를 넘어갔거나, 처음과 끝의 색이 다른 경우(비어있는 경우도 포함)
	if (board[y][x] != color || y < 0 || x < 0 || x >= MAX || y >= MAX) {
		// depth == 5 라면 true 반환, 아니라면 false 반환
		return depth == 5 ? true : false;
	}
	// 방문처리
	v[y][x][dir] = true;

	int ny = y + dy[dir];
	int nx = x + dx[dir];
	return dfs(ny, nx, color, dir, depth + 1);
}

pair<pair<int, int>, int> solve() {
	for (int y = 0; y < MAX; y++) {
		for (int x = 0; x < MAX; x++) {
			// dir[] = { 오른쪽, 아래쪽, 오른쪽 아래, 왼쪽 아래 }
			for (int dir = 0; dir < 4; dir++) {
				if (board[y][x] != 0) { // 오목 판에 흰색 또는 검은색 돌이 올려져 있다면
					if (dfs(y, x, board[y][x], dir, 0)) { // 5목이 되는 지 판단.
						
						// zero-indexing 으로 풀었으므로, 리턴값은 y, x 에 각각 1 씩 더해줘야 함.
						if (dir != 3) {
							return { { y + 1, x + 1 }, board[y][x] };
						}

						// 왼쪽 아래로 오목이 형성된 경우, 시작지점은 왼쪽 아래의 위치임.
						else {
							return { { y + 5, x - 3 }, board[y][x] };
						}
					}
				}
			}
		}
	}

	return { { 0, 0 }, 0 };
}

int main() {
	for (int y = 0; y < MAX; y++) {
		for (int x = 0; x < MAX; x++) {
			cin >> board[y][x];
		}
	}

	pair<pair<int, int>, int> result = solve();
	if (result.second == 0) {
		cout << "0";
	}
	else {
		cout << result.second << "\n";
		cout << result.first.first << " " << result.first.second;
	}

	return 0;
}