도전하라! 시작하라!

아래 그림 1 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형칸들은 하얀색으로 칠해져 있거나 핑크색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 핑크색 색종이를 만들려고 한다.

전체 종이의 크기가 N * N (N = 2^k,k 는 1 이상 7 이하의 자연수)이라면 종이를 자르는 규칙은 다음과 같다.

전체종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간부분을 잘라서 그림 2 의 I,II,III,IV 와 같이 똑같은 크기의 네개의 (N/2) * (N/2) 색종이로 나눈다. 나누어진 종이 I,II,III,IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정으로 잘라진 종이가 모두 하얀색 또는 모두 핑크색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3> 은 <그림 1> 의 종이를 처음 나눈 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9 장의 하얀색 색종이와 7 장의 핑크색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N 과 각 정삭각형의 칸(하얀색 또는 핑크색)이 주어질 때 잘라신 하얀색 색종이와 핑크색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력 형식

• 첫째 줄에는 전체 종이의 한 변의 길이 N 이 주어져 있다. N 은 2,4,8,16,32,64,128 중의 하나이다.
• 색종이의 각 가로줄과 정사각형칸들의 색이 윗줄 부터 차례로 입력의 둘째 줄 부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0 , 핑크색으로 칠해진 칸은 1 로 주어지며 각 숫자사이에는 빈칸이 하나씩 있다.

출력 형식

• 첫째 줄에는 잘라진 하얀색 색종이의 개수를 출력하고
• 둘째 줄에는 핑크색 색종이의 개수를 출력한다.

입출력 예

입력

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

출력

9
7

출처:koi 중등기출

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개의 돌이 연속인 것이 확인 되어 있기 때문이다.