문제 이해 단계
https://www.acmicpc.net/problem/2615
문제는 그냥 우리가 흔히 알고 있는 오목에 관한 문제이다.
흑돌과 백돌의 배치가 주어졌을 때 현재 상태가 누가 이긴 상태인지,
아니면 승부가 나지 않은 상태이지 판가름하는 문제이다.
이 문제 조건에서 5개 연속을 넘은 6개 연속, 7개 연속은 이긴 것으로 판정하지 않는다.
또한 오목이 발생하는 것은 단 하나이며,
흑돌과 백돌이 동시에 이기는 경우는 발생하지 않는다.
중요한 조건은 출력할 때,
가장 왼쪽에 있는 바둑알의 좌표를 출력하는 것이다.
만약 세로로 일자로 놓여있다면 가장 높이 있는 바둑알의 좌표를 출력한다.
문제 접근 단계
이 문제에서 중요한 것은 어떻게 오목을 판정할 것인가에 대한 문제이다.
오목은 5개의 같은 바둑돌이 연속돼야 한다.
그리고 항상 직선의 모양으로 나타나야 한다.
만약 바둑판 가운데에 임의의 바둑알이 하나 있다고 가정했을 때,
해당 바둑알로 만들 수 있는 오목 경로는 다음과 같다.
총 8방위로 모두 가능하다.
중요한 것은 중간에 방향이 변경되면 안 된다는 것이다.
그리고 같은 색의 돌을 놓아야 하기 때문에,
다음에 갈 좌표에도 같은 색의 돌이 있어야 한다.
연속을 체크해 주기 위해서는 그래프 탐색 만한 게 없는 것 같다.
왜냐하면 탐색을 통해 바로 옆에 있는 좌표를 확인할 수 있기 때문이다.
즉, 이 문제는 그래프 탐색을 통해
같은 직선상에 연속되고 같은 색상인 돌이 5개가 있는지를 확인하는 문제이다.
이 직선은 총 8 분위를 직선으로 합치면
4가지 그룹이 나오게 된다.
오목이 발생하는 연속성을 판단하기 위해서는 탐색을 항상 같은 방향으로 진행해야 한다.
왜냐하면 같은 직선상의 연속성을 판단하기 위해서이다.
대각선으로 가고 있었는데 갑자기 오른쪽으로 가거나 아래로 가면
더 이상 직선이 아니게 되어 오목이 아니기 때문이다.
그래서 방향을 정했으면 한 방향으로만 탐색해야 한다.
오른쪽으로 탐색한다면 오른쪽으로만 탐색을 진행하고,
아래만 탐색한다면 아래만 탐색한다.
이렇게 탐색을 하다가
1. 바둑판 밖인 경우
2.0 또는 다른 바둑알이 있는 경우에는
지금까지의 Count값을 반환한다.
Count 값은 탐색한 바둑알이 반복된 횟수이다.
그런데 이 방식으로는 한 가지 문제점이 존재한다.
바로 아래와 같은 상황이다.
가장 왼쪽에 있는 바둑알로는 6개가 연속되기 때문에 오목 조건을 만족시키지 못한다.
하지만, 오목을 찾기 위해 다음 바둑알에 똑같은 탐색을 돌리면
최대 5개로 오목 조건을 만족하게 된다.
왜냐하면 한 방향으로만 움직이기 때문에
오른쪽으로 가면 왼쪽에 있는 하나의 돌은 보지 못하기 때문이다.
사실 왼쪽과 오른쪽은 같은 직선이다. 그래서 이걸 하나의 그룹으로 묶어줘야 한다.
그리고 왼쪽과 오른쪽에서 온 값을 하나로 합쳐야만 비로소 하나의 직선이 된다.
왼쪽과 오른쪽 값을 합칠 수 있는 방법이 필요하고,
또 방향을 정할 수 있는 방법이 필요하다.
그래서 그래프탐색 시작 전에 방향을 정해주고
그 방향으로 그래프 탐색을 돌리고
그 반환값을 받아 더하는 컨트롤타워를 만든다.
예를 들어 이런 식으로 될 것이다.
이런 식으로 구현하면 총 바둑알의 합이 6개가 되어
오목이 되지 않는 것을 확인할 수 있다.
이런 식으로 알고리즘을 세울 것이다.
자세한 구현은 구현문제인 만큼 문제 구현 단계에서 자세히 설명하겠다.
문제 구현 단계
int map[19][19];
// (왼쪽,오른쪽),(위,아래),(좌하단/우상단),(우하단,좌상단)
vector<int> dx[] = {{0,0},{-1,1},{-1,1},{1,-1}};
vector<int> dy[] = {{-1,1},{0,0},{1,-1},{1,-1}};
// 그래프 탐색하여 오목을 찾는 함수
int search(int x, int y, int dir1,int dir2, int count){
if(count > 5) return 999; // 바둑알이 5개가 넘으면 더 이상 탐색 X
// 정해진 방향으로만 움직임
int nx = x + dx[dir1][dir2];
int ny = y + dy[dir1][dir2];
if(nx < 0 || ny < 0 || nx >= 19 || ny >= 19) return count;
// 그 방향에 같은 색 돌이 있을 때만 재귀함수 호출
// 바둑알 갯수 + 1
if(map[nx][ny] == map[x][y]) count = search(nx,ny,dir1,dir2,count+1);
// 지금까지 카운트했던 바둑알 갯수 반환
return count;
}핵심적인 그래프 탐색 함수이다.
같은 방향으로 계속 탐색해 주기 위해서, 깊이 탐색(DFS)을 사용하였다.
같은 직선상에 존재하는 방향은 같은 그룹으로 묶어줘서
오목 판단을 할 때 포함되도록 하였다.
search 함수에서 인자는 좌표 x, y와 dir1, dir2와 count이다.d
ir1과 dir2는 단순히 그냥 전달해 주는 방향이다. 전달받은 방향으로만 움직인다.
count는 현재 바둑알의 총개수이다.
나머지는 일반적인 dfs함수와 같다.
// 그래프 탐색 전에 방향을 정해주는 컨트롤타워
// 그래프 탐색의 결과를 합쳐 오목을 판단
int startSetting(int x, int y){
int ans = 0;
//8방위로 모두 호출
for(int i = 0; i < 4; i++){
int val = 1; // 집합이 다르면 다른 직선으로 보고 초기화
for(int j = 0; j < 2; j++){
int nx = x + dx[i][j];
int ny = y + dy[i][j];
if(nx < 0 || ny < 0 || nx >= 19 || ny >= 19) continue;
// 같은 그룹에 있는 양방향으로 search 함수 호출
if(map[x][y] == map[nx][ny]) val += search(nx,ny,i,j,1);
}
// 바둑알이 5개 일때만
if(val == 5) {
ans = map[x][y]; // 해당 바둑알의 색깔 반환
break;
}
}
return ans;
}위에서 언급했던 방향을 정해주고
그래프 탐색의 결과를 반환받아 합쳐주는 컨트롤 타워이다.
여기서 모든 방향에 대한 그래프 탐색을 호출하여
방향별로 DFS를 발생시켜 함수를 호출한다.
여기서 주의 깊게 봐야 하는 것은
val이라는 값이 이중 반복문 중 첫 번째 반복문에서 초기화된다는 점이다.
즉, 같은 그룹에 있는 것은 동일한 직선으로 판단되고,
다른 그룹에 있는 것은 그렇지 않다는 것이다.
그리고 매 val 합의 값이 5가 나오면 오목이 발생한 것이므로
더 이상 반복 필요 없이 그 바둑알의 색을 반환한다.
이제 아래는 전체 코드를 올리고
전체 코드에 대한 조금의 설명을 하고 마치겠다.
#include <iostream>
#include <vector>
using namespace std;
int map[19][19];
// (왼쪽,오른쪽),(위,아래),(좌하단/우상단),(우하단,좌상단)
vector<int> dx[] = {{0,0},{-1,1},{-1,1},{1,-1}};
vector<int> dy[] = {{-1,1},{0,0},{1,-1},{1,-1}};
// 그래프 탐색하여 오목을 찾는 함수
int search(int x, int y, int dir1,int dir2, int count){
if(count > 5) return 999; // 바둑알이 5개가 넘으면 더 이상 탐색 X
// 정해진 방향으로만 움직임
int nx = x + dx[dir1][dir2];
int ny = y + dy[dir1][dir2];
if(nx < 0 || ny < 0 || nx >= 19 || ny >= 19) return count;
// 그 방향에 같은 색 돌이 있을 때만 재귀함수 호출
// 바둑알 갯수 + 1
if(map[nx][ny] == map[x][y]) count = search(nx,ny,dir1,dir2,count+1);
// 지금까지 카운트했던 바둑알 갯수 반환
return count;
}
// 그래프 탐색 전에 방향을 정해주는 컨트롤타워
// 그래프 탐색의 결과를 합쳐 오목을 판단
int startSetting(int x, int y){
int ans = 0;
//8방위로 모두 호출
for(int i = 0; i < 4; i++){
int val = 1; // 집합이 다르면 다른 직선으로 보고 초기화
for(int j = 0; j < 2; j++){
int nx = x + dx[i][j];
int ny = y + dy[i][j];
if(nx < 0 || ny < 0 || nx >= 19 || ny >= 19) continue;
// 같은 그룹에 있는 양방향으로 search 함수 호출
if(map[x][y] == map[nx][ny]) val += search(nx,ny,i,j,1);
}
// 바둑알이 5개 일때만
if(val == 5) {
ans = map[x][y]; // 해당 바둑알의 색깔 반환
break;
}
}
return ans;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int ans, ansX, ansY;
ans = 0;
ansX = ansY = 99;
for(int i = 0; i < 19; i++)
for(int j = 0; j < 19; j++) cin >> map[i][j];
for(int i = 0; i < 19; i++){
for(int j = 0; j < 19; j++){
if(map[i][j] != 0){
int val = startSetting(i,j);
if(val != 0) {
// 가장 왼쪽에 있는 바둑알로 갱신해주기 위함
// 가장 위에 있는 바둑알은 어차피 위에서부터 탐색해서
// 따로 처리안해줘도 됨
if(j < ansY){
ans = val;
ansX = i;
ansY = j;
}
}
}
}
}
if(ans){
cout << ans << "\n";
cout << ansX+1 <<" " << ansY+1;
}
else cout << "0";
}핵심적으로 봐야 하는 것은 val 값이 나왔다고 해서
바로 종료해 주는 것이 아닌 끝까지 실행시켜 주는 것이다.
이는 크기가 19x19로 정해져 있기 때문에 브루트포스로도 풀 수 있어
시간적 부담이 없기 때문인 것이 첫번째 이유다.
두번째 이유는 문제 조건에서 가장 왼쪽에 있는 바둑알의 좌표를
출력해 달라고 했기 때문에 이를 최신화해 주기 위함이다.
그리고 좌표 x, y를 0부터 시작했기 때문에
답을 출력할 때는 1씩 더해준다.
시행착오
문제를 잘못 이해해서 엄청나게 낭패를 본 문제이다.
푸는 것 자체는 그렇게 오래 걸린 거 같진 않은데,
가장 왼쪽에 있는 걸 출력하는 걸 이상하게 이해해서 애먹었다.
아무리 테스트케이스를 넣어봐도 맞게 떠서.. 그냥 뻘짓거리 좀 많이 한 것 같다.
그래도 엄청난 수확이 있었는데,
백준에서 사용하기 좋은 사이트를 발견했다는 것이다.
JUNGOL
www.jungol.co.kr
여기서 백준 문제를 제출하면 프로그래머스처럼 점수로 볼 수 있을 뿐만 아니라,
틀리면, 오답이 나오는 예제 케이스를 만들어준다!
문제는 안 풀리고 그렇다고
답 보기는 싫을 때 해당 사이트를 이용하면 좋을 것 같다,