https://www.acmicpc.net/problem/2615
19 × 19 크기의 바둑판에 같은 색의 바둑알이 연속으로 다섯 알이 놓여 있는 경우 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 아래의 그림은 검은색이 이긴 경우이다. 그러나 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지, 또는 아직 승부가 결정되지 않았는지를 판단하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 검은색과 흰색이 동시에 이기거나, 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.
- 검은색 또는 흰색이 이겼을 경우에는 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와 세로줄 번호를 순서대로 출력한다.
바둑알이 놓여 있는 좌표마다 해당 좌표와 바둑알의 색을 오목 확인용 함수에 파라미터로 넘긴다. →, ↓, ↘, ↙의 네 방향을 검사하면서 다섯 개의 바둑알이 놓였는지 확인하고, 오목이 된 경우에 육목인지까지 추가로 확인해야 한다. 가장 왼쪽에 있는 바둑알의 좌표와 색을 출력해야 하므로, 오목인지 확인하면서 vector에 바둑알 좌표를 해야 한다. 열, 행이 순서대로 오름차순이 되도록 정렬하고, vector의 가장 앞에 있는 좌표를 출력하고 프로그램을 종료시키면 된다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- 바둑판 정보 입력받기
- 바둑판에서 1(검은색) 또는 2(흰색)인 위치에서 →, ↓, ↘, ↙의 네 방향을 검사하면서 다섯 개의 바둑알이 놓였는지 확인하기
- 다섯 개가 놓여있는 경우, 육목이 됐는지도 확인하고 육목이 아닌 경우엔 바둑알의 색(1 또는 2)과 좌표를 출력하고 프로그램 종료하기
- 오목을 찾지 못한 경우 0 출력하기
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
1~4회차
- 오목 확인용 함수에서, 육목까지 확인하고 답을 출력한 뒤 프로그램을 종료하도록 설계하는 게 코드를 더 깔끔하게 만들 수 있음
- 좌표마다 8방향을 확인하면 오목인지를 중복으로 확인하게 됨
- →, ↓, ↘, ↙의 네 방향만 검사하도록 수정
- 육목인지 확인할 때,
- 0, 1, 1, 1, 1, 1, 0를 예로 들면, 0번째에 있는 수와 6번째에 있는 수가 각각 1과 다른지 한 번에 확인해야 함
- 바둑판을 board[21][21]로 넉넉하게 선언해야 OutOfBounds 에러가 발생하지 않음
정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
int board[21][21],dx[4]={0,1,1,1},dy[4]={1,0,1,-1};
bool cmp(pii x, pii y) {
if (x.second==y.second) return x.first<y.first;
else return x.second<y.second;
}
void check(int x, int y, int bw) {
for (int d=0; d<4; d++) {
int tmp_x=x,tmp_y=y;
bool flag = true;
vector<pii> v;
v.push_back({x,y});
for (int i=1; i<=4; i++) {
tmp_x+=dx[d];
tmp_y+=dy[d];
if (tmp_x<=0 || tmp_y<=0 || tmp_x>19 || tmp_y>19 || board[tmp_x][tmp_y]!=bw) {
flag = false;
break;
}
v.push_back({tmp_x,tmp_y});
}
if (flag) {
tmp_x+=dx[d];
tmp_y+=dy[d];
if (board[tmp_x][tmp_y]!=bw && board[x-dx[d]][y-dy[d]]!=bw) {
sort(v.begin(),v.end(),cmp);
cout << bw << '\n' << v[0].first << ' ' << v[0].second;
exit(0);
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for (int i=1; i<=19; i++)
for (int j=1; j<=19; j++) cin >> board[i][j];
for (int i=1; i<=19; i++)
for (int j=1; j<=19; j++)
if (board[i][j]!=0) check(i,j,board[i][j]);
cout << 0;
}