문제
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.
위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.
입력
19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.
출력
첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.
https://www.acmicpc.net/problem/2615
풀이
이전 포스팅에서 오목 금수 알고리즘을 짜본적이있었다.
https://velog.io/@cldhfleks2/java%EC%98%A4%EB%AA%A9-%EA%B8%88%EC%88%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
하지만 이문제에서는 삼삼, 사사는 제외, 오목과 육목을 구분하여 오목일때 누가 특정좌표에서 승리하도록 구하면된다.
특정좌표
- 가로줄일경우 제일 좌측좌표
- 세로줄일경우 제일 상단 좌표
- 대각선일경우 제일 좌측 좌표(대각선 방향에 무관)
- 출력을 하는 부분
- 정수(흑 : 1 백 : 2)가 이기는지, 이기면 좌표를 리턴하는 find함수
2-1. 가로줄방향 check
해당돌을 찾을때마다 cnt를 더하고, 해당돌을 못찾았을때마다 cnt가 5인지 확인하며 좌표를 리턴해주었다. 이때 i, j-5인이유는 출력하는부분에 모든좌표 + 1 을 했기때문임
2-2. 세로줄 방향 check
map의 행과 열을 바꾸어 탐색한다. 위와 동일
2-3. 대각선 ＼ check
이때 i, j 는 비교하고자하는 대각선의 좌상단 시작좌표이다. 여기서부터 gap을 추가하며 다음대각선위치에 돌이있는가를 확인한다. 앞의 가로줄, 세로줄방향도 이와같은 원리로 코드를 짰어도 괜찮았을것같다.
이때 중요한것은 우하단방향으로 탐색하므로, 좌상단방향에 이미 같은색의 돌이 놓인경우 같은 대각선라인을 두번 탐색하므로 이런경우는 continue 해주었다.
2-4. 대각선 / check
원리는 위와같으나, 시작좌표 i, j 의 범위가 다르다.
정답률이 낮을만하게 예외상황들을 잘 고려해서 처리해주어야한다. 처음부터 시작좌표를 i, j 로 잡고서 대각선방향(우하단, 좌하단)이든 가로줄(우측)이든 세로줄(하측)이든 탐색하는것을 추천한다.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using std::pair;
int** map;
//흑 또는 백이 이기는 수를 찾아서 리턴
pair<int, int> find(int n) {
int x = -1, y = -1;
int cnt = 0; //얼마나 연속되는지 확인
// ㅡ
for (int i = 0; i < 19; i++) {
int j;
for (j = 0; j < 19; j++) {
if (map[i][j] == n) { //찾고자하는 돌을 찾았으면
cnt++; //연속된 갯수
}
else {
if (cnt == 5) { //정확히 5개 일때만 승리
//printf("11\n");
return { i, j - 5 }; //좌단 위치 리턴 (한번지나치고나서 이므로 j-5)
} //6개이상 놓인경우였으면 제외
cnt = 0;
}
}
if (cnt == 5) { //정확히 5개 일때만
//printf("111\n");
return { i, j - 5 }; //좌단 위치 리턴
}
cnt = 0; //다음열로 가면 초기화
}
cnt = 0; //초기화
// |
for (int i = 0; i < 19; i++) {
int j;
for (j = 0; j < 19; j++) {
if (map[j][i] == n) {
cnt++;
}
else {
if (cnt == 5) {
//printf("22\n");
return { j - 5, i }; //상단 위치 리턴 (한번 지나쳤으므로 j-5)
}
cnt = 0;
}
}
if (cnt == 5) {
//printf("222\n");
return { j - 5, i }; //상단 위치 리턴
}
cnt = 0; //다음열로 가면 초기화
}
cnt = 0;
// ＼
for (int i = 0; i < 19 - 4 ; i++) { //좌상단 x 위치
for (int j = 0; j < 19 - 4; j++) { //좌상단 y 위치
cnt = 0; //초기화
if (i != 0 && j != 0) {
//현재 i, j 바로직전 좌상단이 같은돌이면 이미 탐색했으므로 제외
if (map[i - 1][j - 1] == n)
continue;
}
for (int gap = 0; ; gap++) { //5번씩 우하단으로 감
if (i + gap == 19 || j + gap == 19) //범위 벗어나면 스탑
break;
if (map[i + gap][j + gap] != n) { //아닌것을찾으면 스탑
if (cnt == 5) { //정확히 5개일때만 승리한것
//printf("33\n");
return { i, j }; //좌상단위치 리턴
}
cnt = 0;
break;
}
cnt++;
}
if (cnt == 5) { //정확히 5개일때만 승리한것
//printf("333\n");
return { i, j }; //좌상단위치 리턴
}
}
}
cnt = 0;
// /
for (int i = 0; i < 19 - 4; i++) {
for (int j = 0 + 4; j < 19; j++) {
cnt = 0;
if (i != 0 && j != 18) {
//현재 i, j 바로직전 우상단이 같은돌이면 이미 탐색했으므로 제외
if (map[i - 1][j + 1] == n)
continue;
}
for (int gap = 0; ; gap++) {
if (i + gap == 19 || j - gap == -1)
break;
if (map[i + gap][j - gap] != n) {
if (cnt == 5){
//printf("44\n");
return { i + 4, j - 4 }; //좌하단 위치
}
cnt = 0;
break;
}
cnt++;
}
if (cnt == 5) {
//printf("444\n");
return { i + 4, j - 4 }; //좌하단 위치
}
}
}
//만약못찾았으면 { -1, -1 } 리턴
return { x, y };
}
int main(void) {
map = new int* [19];
for (int i = 0; i < 19; i++) { //입력받음
map[i] = new int[19];
for (int j = 0; j < 19; j++)
scanf("%d", &map[i][j]);
}
pair<int, int> res = find(1);
if (res.first == -1) { //흑이 지면
res = find(2);
if (res.first == -1) { //백이 지면
printf("0"); //승부결정이 안났음
return 0;
}
else { //백이 이긴경우
printf("2\n%d %d", res.first + 1, res.second + 1);
return 0;
}
}
else { //흑이 이긴경우
printf("1\n%d %d", res.first + 1, res.second + 1);
return 0;
}
return 0;
}