BaekJoon 2615번: 오목(C++)

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

2615번: 오목

풀이법

1) 문제에서 주어진 정의에 따라 알맞게 구현하는 것이 가장 핵심이었던 문제이다. 세로로 일자인 것을 제외하고는 가장 왼쪽에 있는 돌의 위치를 출력해야 한다는 점과, 육목(6개가 연결되는 것)이 되면 안된다는 점을 제대로 인지해야 풀 수 있는 문제였다.

2) dfs()기반의 재귀 알고리즘을 사용했지만, visited배열과 같은 방문한 곳을 check하지 않았기에 제대로된 dfs알고리즘을 사용한 것은 아니다. 가장 왼쪽의 행과 열의 index를 찾아야 했기에, 탐색 방향은 동,남동,남,북동 과 같이 4개의 방향을 탐색해 주었다.

int vx[4] = { 0,1,1,-1 };
int vy[4] = { 1,1,0,1};

3) 육목을 방지하기 위해, 앞서 설명한 방향대로 진행할 수 있는 경우, 정 반대의 방향에도 갈 수 있는 길이 있는지를 prevX와 prevY를 통해 확인했다. 예를 들자면, 현재에서 동쪽으로 진행할 수 있는 경우, 서쪽에도 나와 같은 색의 돌이 있는지 체크를 함을 통해 가장 왼쪽의 돌을 고르려고 코딩을 진행했다.

4) 구현 문제이기에 장황한 설명보다 코드를 직접 읽고 이해하는 것이 더 도움이 되리라 생각한다.

#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
#define INF 987654321
using namespace std;
int arr[20][20];

int vx[4] = { 0,1,1,-1 };
int vy[4] = { 1,1,0,1};
int answer = 0;
int ansX, ansY;
bool check = false;

void dfs(int a, int b, int wb, int cnt,int dir)
{
	if (cnt == 5)
	{
		int nextX = a + vx[dir];
		int nextY = b + vy[dir];
		if (nextX >= 1 && nextY >= 1 && nextX <= 19 && nextY <= 19)//진행하던 방향대로 더 갈 수 있는 경우
		{
			if (arr[nextX][nextY] != wb)
			{
				answer = wb;
				check = true;
				return;
			}
		}
		else//진행하던 방향이 범위 밖이면
		{
			answer = wb;
			check = true;
			return;
		}
	}
	else
	{
		int nextX = a + vx[dir];
		int nextY = b + vy[dir];
		if (nextX >= 1 && nextY >= 1 && nextX <= 19 && nextY <= 19)
		{
			if (arr[nextX][nextY] == wb )
			{
				dfs(nextX, nextY, wb, cnt + 1, dir);
			}
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	for (int i = 1; i <= 19; i++)
		for (int j = 1; j <= 19; j++)
			cin >> arr[i][j];

	for (int i = 1; i <= 19; i++)
	{
		for (int j = 1; j <= 19; j++)
		{
			if (arr[i][j] == 1)//흰색
			{
				for (int k = 0; k < 4; k++)
				{
					int nextX = i + vx[k];
					int nextY = j + vy[k];
					if (nextX >= 1 && nextY >= 1 && nextX <= 19 && nextY <= 19)
					{
						if (arr[nextX][nextY] == 1)//진행할 수 있는 경우
						{
							int prevX = 0;
							int prevY = 0;
							if (k == 0)
							{
								prevX = i;
								prevY = j - 1;
							}
							else if (k == 1)
							{
								prevX = i-1;
								prevY = j - 1;
							}
							else if (k == 2)
							{
								prevX = i-1;
								prevY = j;
							}
							else
							{
								prevX = i + 1;
								prevY = j - 1;
							}
							if (prevX >= 1 && prevY >= 1 && prevX <= 19 && prevY <= 19)
							{
								if (arr[prevX][prevY] == 1)
									continue;
							}
							dfs(nextX, nextY, 1, 2,k);
							if (check == true)
							{
								ansX = i;
								ansY = j;
								cout << answer << "\n";
								cout << ansX << " " << ansY;
								return 0;
							}
						}
					}
				}
			}
			else if (arr[i][j] == 2)//검은색
			{
				for (int k = 0; k < 4; k++)
				{
					int nextX = i + vx[k];
					int nextY = j + vy[k];
					if (nextX >= 1 && nextY >= 1 && nextX <= 19 && nextY <= 19)//진행할 수 있는 경우
					{
						if (arr[nextX][nextY] == 2)
						{
							int prevX = 0;
							int prevY = 0;
							if (k == 0)
							{
								prevX = i;
								prevY = j - 1;
							}
							else if (k == 1)
							{
								prevX = i - 1;
								prevY = j - 1;
							}
							else if (k == 2)
							{
								prevX = i - 1;
								prevY = j;
							}
							else
							{
								prevX = i + 1;
								prevY = j - 1;
							}
							if (prevX >= 1 && prevY >= 1 && prevX <= 19 && prevY <= 19)
							{
								if (arr[prevX][prevY] == 2)
									continue;
							}
							dfs(nextX, nextY, 2, 2,k);
							if (check == true)
							{
								ansX = i;
								ansY = j;
								cout << answer << "\n";
								cout << ansX << " " << ansY;
								return 0;
							}
						}
					}
				}
			}
		}
	}
	cout << answer;

}