멤고리즘 3회 1번. 오목 (재귀)

병훈이의 오목

문제

  

병훈이는 자신이 만든 오목 대전시스템에 자부심을 갖고 있다. 다음 단기에도 AI대회를 위해 후계자를 양성해야 한다.

바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, …, 19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, …, 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알이 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다. 입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오.

단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

프로그램의 실행시간은 1초를 넘을 수 없다. 

 

입력

입력 파일은 19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않은 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.

출력

첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다.

검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그중 가장 위에 있는 것)의 가로줄 번호와 세로줄 번호를 순서대로 출력한다.

 

예제 입력​

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0 
0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

예제 출력

1
3 2

출제자 : 임현수

---

[문제 풀이]

일반적으로 모두가 알고 있는 오목과 같은 룰이다.

오목은 어느 방향으로든 같은 색의 돌이 연속으로 5개가 놓이면 승리하는 게임이다.

가로로 놓일 경우 제일 왼쪽의 돌을, 대각선으로 놓일 경우 제일 위쪽의 돌을 기준으로 연속인지 확인한다.

다만, 주의할 점은 연속으로 6개가 놓이면 이긴것이 아니다. (아래에서는 이런 경우를 6돌이라 부르겠다.)

[소스코드 풀이]

x와 y의 좌표가 (0, 0) 이 아닌 (1, 1)부터 시작하게 하기 위해서 처음 map을 선언할 때 MAX+1을 해주고 0으로 초기화하였다.

- bool 타입의 chk 함수

x, y : 좌표

d : 방향

count : 개수

color : 선택한 색깔

일단, 처음에 맵의 크기를 넘어서는지를 확인하면서 6돌인지를 확인한다.

그리고 다음 돌이 현재 선택된 돌과 같은색인지를 체크하는 if문을 만들었다.

여기서 d의 경우 한 시부터 시계 방향으로 각 각 1~4의 방향이고 이 외의 것을 0으로 생각한다.

1~4 이외의 방향인 0의 경우 각 방향별로 반대 방향에 돌이 있는지를 확인하는 case 0: 을 작성합니다.

그리고 재귀로 chk함수를 계속 돌면서 count가 늘어나게 되는데

6목의 경우 이긴경우가 아니라고 했는데 count가 6일 경우에 true를 줬을까요?

그건 바로 count가 6까지 증가를 하고 chk()에 들어왔을 때에 5개의 돌이 연속인 것이 확인 되어 있기 때문이다.

주의! 

우리가 일반적으로 수학에서 배운 좌표계와 배열에서 사용하는 좌표계는 다릅니다!

밑에 표에서 보시는 바와 같이 오른쪽과 아래쪽으로 갈수록 크기가 커집니다.

y   /   x	0	1	2
0	0	0	1
1	1	2	1
2	3	1	0

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

#include <iostream> #define MAX 19   using namespace std;   int map[MAX + 1][MAX + 1] = { { 0, 0 } };   //d:방향, count:갯수 bool chk(int y, int x , int d, int count, int color) {     //count 6까지 가봐야 돌이 있는지 알 수 있으니까 count > 6     if (x < 0 || y < 0 || x > MAX + 1 || y > MAX + 1 || count > 6)         return false;       if (map[y][x] == color){         switch (d) {             //방향x         case 0:             //순서대로 1번방향에 돌이 있고 반대 방향에 돌이 같은 색이 아닐때             return ((map[y + 1][x - 1] != color) && chk(y - 1, x + 1, 1, 2, color))                 || ((map[y][x - 1] != color) && chk(y, x + 1, 2, 2, color))                 || ((map[y - 1][x - 1] != color) && chk(y + 1, x+1, 3, 2, color))                 || ((map[y - 1][x] != color) && chk(y + 1, x, 4, 2, color));             //방향 o, 1시방향부터 1         case 1:             return chk(y - 1, x + 1, d, count+1, color);         case 2:             return chk(y, x + 1, d, count+1, color);         case 3:             return chk( y + 1, x + 1, d, count+1, color);         case 4:             return chk(y + 1, x, d, count+1, color);         }     }     else {         if (count == 6)             return true;     }     return false; }   int main() {     for (int i = 1; i < 20; i++){         for (int j = 1; j < 20; j++)             cin >> map[i][j];     }       for (int i = 1; i < 20; i++){         for (int j = 1; j < 20; j++) {             // 바둑 있냐             if (map[i][j] > 0) {                 //오목                 if (chk(i, j, 0, 1, map[i][j])) {                     cout << map[i][j] << endl << i << " " << j;                     return 0;                 }             }         }     }     //비김     cout << 0;     return 0; }