문제
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.
위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.
입력
19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.
출력
첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.
코드
/**
* @author 조현수
* @date 24.01.29
* @link https://www.acmicpc.net/problem/2615
* @keyword_solution 완전탐색, 현재 위치로부터 4개의 방향 탐색하면서 내려가기
* 1. 바둑알 정보를 체크해서 승자 확인 또는 아직 결정되지 않았는지 확인
* 1-1. 둘이 동시에 이기거나 두 군데 이상에서 이기는 경우는 X
* 2. 5목 (6목 X) -> 제한사항 체크
* 3. 출력할 때 가장 왼쪽 위의 시작좌표를 출력 -> 순차적으로 내려가야겠다고 생각
* @input 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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
* @output 1
* 3 2
* @time_complex O(N ^ 2)
* @perf 메모리 19220 시간 272
*/
public class 백준_2615_오목 {
static int[][] data = new int[20][20];
static int startX, startY;
static int winColor;
static int dx[] = {0, 1, 1, -1};
static int dy[] = {1, 0, 1, 1};
static StringTokenizer st;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("input.txt"));
// 여기에 코드를 작성하세요.
Scanner sc = new Scanner(System.in);
for (int i = 1; i <= 19; i++) {
for (int j = 1; j <= 19; j++) {
data[i][j] = sc.nextInt();
}
}
boolean flag = false; // 경기를 누군가가 이겼다면 true, 아니면 false 유지
outer:
for (int i = 1; i <= 19; i++) {
for (int j = 1; j <= 19; j++) {
// 현재 좌표에서 검사 진행
if (data[i][j] == 1) {
for (int d = 0; d < 4; d++) {
if (BFS(i, j, 1, d)) {
flag = true; // 검은돌이 이김
startX = i;
startY = j;
winColor = 1;
break outer;
}
}
} else if (data[i][j] == 2) {
for (int d = 0; d < 4; d++) {
if (BFS(i, j, 2, d)) {
if (BFS(i, j, 2, d)) {
flag = true;
startX = i;
startY = j;
winColor = 2;
break outer;
}
}
}
}
}
}
if (flag) {
System.out.println(winColor);
System.out.println(startX + " " + startY);
} else {
System.out.println(0);
}
}
public static boolean BFS(int x, int y, int color, int d) { // 시작 좌표 x,y , 색깔, 방향 d
int cnt = 1;
int nx = x, ny = y;
for (int i = 0; i < 4; i++) {
nx += dx[d];
ny += dy[d];
if (isInner(nx, ny) && data[nx][ny] == color) {
cnt += 1;
} else {
break;
}
}
if(cnt != 5) return false; // 5개 확인했는데 아니면 일단 그냥 아님.
// 시작점 끝점 예외처리
nx += dx[d]; ny += dy[d];
// 끝점 예외처리
if (isInner(nx, ny) && data[nx][ny] == color) {
return false;
}
x -= dx[d]; y -= dy[d];
// 시작점 예외처리
if (isInner(x, y) && data[x][y] == color) {
return false;
}
return true;
}
public static boolean isInner(int i, int j) {
if (i < 1 || i > 19 || j < 1 || j > 19) {
return false;
}
return true;
}
public static boolean checkRight(int x, int y, int color) {
int cnt = 0;
for (int i = 0; i < 5; i++) {
if (isInner(x, y + i) && data[x][y + i] == color) {
cnt += 1;
}
}
if (cnt != 5) return false;
if (cnt == 5) {
// 여기서 이제 유효성 검사 진행
if (isInner(x, y - 1) && (data[x][y - 1] == color)) {
return false;
}
if (isInner(x, y + 5) && data[x][y + 5] == color) {
return false;
}
}
return true;
}
public static boolean checkDown(int x, int y, int color) {
int cnt = 0;
for (int i = 0; i < 5; i++) {
if (isInner(x + i, y) && data[x + i][y] == color) {
cnt += 1;
}
}
if (cnt != 5) return false;
if (cnt == 5) { // 시작점 -1, 끝점 + 1 기준으로 검사해야함
if (isInner(x - 1, y) && data[x - 1][y] == color) {
return false;
}
if (isInner(x + 5, y) && data[x + 5][y] == color) {
return false;
}
}
return true;
}
public static boolean checkDiagonalDown(int x, int y, int color) {
int cnt = 0;
for (int i = 0; i < 5; i++) {
if (isInner(x + i, y + i) && data[x + i][y + i] == color) {
cnt += 1;
}
}
if (cnt != 5) return false;
if (cnt == 5) { // 시작점 -1, 끝점 + 1 기준으로 검사해야함
if (isInner(x - 1, y - 1) && data[x - 1][y - 1] == color) {
return false;
}
if (isInner(x + 5, y + 5) && data[x + 5][y + 5] == color) {
return false;
}
}
return true;
}
public static boolean checkDiagonalUp(int x, int y, int color) {
int cnt = 0;
for (int i = 0; i < 5; i++) {
if (isInner(x - i, y + i) && data[x - i][y + i] == color) {
cnt += 1;
}
}
if (cnt != 5) return false;
if (cnt == 5) { // 시작점 -1, 끝점 + 1 기준으로 검사해야함
if (isInner(x + 1, y - 1) && data[x + 1][y - 1] == color) {
return false;
}
if (isInner(x - 5, y + 5) && data[x - 5][y + 5] == color) {
return false;
}
}
return true;
}
}코멘트
문제에서 누가 이겼는지 확인하자는 내용. → 2차원 배열 완전탐색 해야겠다고 생각. : 브루트포스 문제
처음에는 모든 방향에 대해 각각 메서드를 만들었음 (checkRight, checkDown….)
근데 다시 보니 그럴 필요 없이 BFS 메서드 하나 만들고 방향벡터 dx,dy 적용시켜서 풀면 간단하게 풀렸다.
여기서 내가 왜 각 좌표별로 8방 탐색을 안했는지 → 해당 문제는 일반적인 DFS, BFS처럼 예측 불가능한 경로를 보는게 아니라, 정확하게 딱 현재 좌표 포함 5개의 좌표만 확인하면 된다. 그렇기에 8가지 방향을 모두 탐색하면 중복이 매우 많이 생긴다.
그래서 왼쪽 위부터 순차적으로 내려오면서 4가지 방향만 (오른쪽, 아래, 오른쪽 아래 대각선, 오른쪽 위 대각선) 탐색하면 중복되지 않고 깔끔하게 탐색할 수 있다.
- 또한 문제에서 6목은 안된다고 했으니 5목 완성 후에 예외처리 시작점, 끝점 기준으로 해줬으면 됐다.
