[BOJ] 백준 2615번: 오목 _자바(JAVA)
1. 문제
https://www.acmicpc.net/problem/2615
2. 접근 및 해결
2-1) 접근
현재 도달한 배열의 좌표(i,j)를 기준으로 세로줄, 가로줄, 대각선, 역대각선을 만들어서 오목을 확인했습니다.
세로줄(ㅣ), 가로줄(ㅡ), 역대각선(\)에 대해 index 확인을 그림으로 나타내면 아래와 같습니다.
1. 세로줄(ㅣ)
list[i][j] -> list[i+1][j] -> list[i+2][j] ... 로 i값만 +1 변경됩니다.
2. 가로줄(ㅡ)
list[i][j] -> list[i][j+1] -> list[i][j+2] ... 로 j값만 +1 변경됩니다.
4. 역대각선(\)
list[i][j] -> list[i+1][j+1] -> list[i+2][j+2] ... 로 i, j값이 각각 +1 변경됩니다.
대각선에 대해서는 아래와 같습니다.
3. 대각선(/)
list[i][j] -> list[i+1][j-1] -> list[i+2][j-2] ... 로 i는 +1, j는 -1 변경됩니다.
이런식으로 오목과 6목을 계산할겁니다.
2-2) 해결
주요 메소드는 2가지가 있습니다.
- boolean checkFive(int color, int i, int j, int dx, int dy); // 오목 확인
- boolean isNotSix (int color, int i, int j, int dx, int dy); // 6목 확인
1. checkFive 메소드
오목인지 확인하는 메소드입니다.
위에서 접근했던 방식대로 변경되는 값 만큼을 dx, dy로 넘겨 계산합니다.
코드 작성 시 무조건 list의 index가 넘어가지 않는 범위를 파라미터로 넣어줄 것이라,
메소드에서 i+k*dx, j+k*dy의 범위를 검사하지 않아도 됩니다.
현재 i,j에서 세로줄 오목이 가능한지 확인하려할 때는 i<=14를 미리 검사합니다.
똑같이 가로줄 확인 시 j <= 14, 대각선(/) 확인 시 i<=14 && j>=4, 역대각선(\) 확인 시 i<=14 && j<=14를 미리 검사하여 현재 메소드에서 무조건 오목이 되는 경우만 검사할 수 있게 합니다.
2. isNotSix 메소드
6목인지 확인하는 메소드입니다.
6목은 2가지 방법이 될 수가 있는데 현재 i,j를 기준으로 이전값, 이후값을 모두 검사해야합니다.
여기서 이전값은 세로줄 검사에서 i=1, j=0이라 가정하면 i=0, j=0이 이전값이고 i=6, j=0이 이후값입니다.
이전값과 이후값이 모두 현재 오목 색과 다른지 확인하고 둘다 다르다면 6목이 아닌 것으로 판별하게됩니다.
3. 코드(JAVA)
전체 코드는 아래와 같습니다.
import java.io.*;
import java.util.*;
public class Main {
static int[][] list;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
list = new int[19][19];
for (int i = 0; i < 19; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 19; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
int egg = -1; // 흰알 or 검은알
int x = -1, y = -1; // 오목의 가장 왼쪽에 있는 바둑알의 x좌표, y좌표
// 바둑판 순환
for (int i = 0; i < 19; i++) {
for (int j = 0; j < 19; j++) {
if (list[i][j] == 0) continue; // color가 0인 경우 검사X - 어떤 알도 아니기 때문
int color = list[i][j];
// 세로줄 확인
if (i <= 14) { // 세로줄은 x좌표가 15이상이 되면 오목이 불가능함(최대 4개까지밖에 못 놓음)
if (checkFive(color, i, j, 1, 0)) { // 오목 가능한지 확인
if (isNotSix(color, i, j, 1, 0)) { // 6목 아닌지 확인
egg = color;
x = i;
y = j;
break;
}
}
}
// 가로줄 확인
if (j <= 14) { // 가로줄은 y좌표가 15이상이 되면 오목이 불가능함(최대 4개까지밖에 못 놓음)
if (checkFive(color, i, j, 0, 1)) {
if (isNotSix(color, i, j, 0, 1)) {
egg = color;
x = i;
y = j;
break;
}
}
}
// 대각선(/) 확인
if (i <= 14 && j >= 4) { // 대각선은 x가 15이상, j가 4미만이 되면 오목이 불가능함(최대 4개까지밖에 못 놓음)
if (checkFive(color, i, j, 1, -1)) {
if (isNotSix(color, i, j, 1, -1)) {
egg = color;
x = i + 4; // 가장 위에 좌표를 탐색하므로, 대각선(/)기준으로 x는 +4 이동,
y = j - 4; // y는 -4만큼 이동해야 오목에서 가장 왼쪽의 좌표를 찾을 수 있음
break;
}
}
}
// 역대각선(\) 확인
if (i <= 14 && j <= 14) { // 역대각선은 x가 14이상, j가 14이상이 되면 오목이 불가능함(최대 4개까지밖에 못 놓음)
if (checkFive(color, i, j, 1, 1)) {
if (isNotSix(color, i, j, 1, 1)) {
egg = color;
x = i;
y = j;
break;
}
}
}
}
if (egg > 0) break; // egg에 양수가 들어간 것은 오목이 만들어진 것
}
if (egg > 0) { // 오목이 되면
bw.write(egg + "\n");
bw.write((x + 1) + " " + (y + 1));
} else {
bw.write("0");
}
br.close();
bw.close();
}
/**
* 5목 확인 메소드
* @param color 현재 색상(1, 2)
* @param x index i
* @param y index j
* @param dx 확인할 x좌표[1, 0, 1, 1] // 세로, 가로, 대각선(/), 역대각선(\)
* @param dy 확인할 y좌표[0, 1, -1, 1] // 세로, 가로, 대각선(/), 역대각선(\)
* @return
*/
static boolean checkFive(int color, int x, int y, int dx, int dy) {
for (int k = 0; k < 5; k++) {
if (list[x + k * dx][y + k * dy] != color) {
return false;
}
}
return true;
}
/**
* 6목 확인 메소드
* @param color 현재 색상(1, 2)
* @param x index i
* @param y index j
* @param dx 확인할 x좌표[1, 0, 1, 1] // 세로, 가로, 대각선(/), 역대각선(\)
* @param dy 확인할 y좌표[0, 1, -1, 1] // 세로, 가로, 대각선(/), 역대각선(\)
* @return
*/
static boolean isNotSix(int color, int x, int y, int dx, int dy) {
int pX = x - dx; // 오목 기준으로 이전 값 확인
int pY = y - dy;
int nX = x + 5 * dx; // 오목 기준으로 더 떨어진 값 확인
int nY = y + 5 * dy;
boolean isPNotSix = (pX < 0 || pY < 0 || pX >= 19 || pY >= 19 || list[pX][pY] != color); // index를 벗어나지 않고, 해당 위치가 현재 색과 달라야 함
boolean isNNotSix = (nX < 0 || nY < 0 || nX >= 19 || nY >= 19 || list[nX][nY] != color);
return isPNotSix && isNNotSix; // 둘다 조건 만족 시 6목이 아님을 반환(true)
}
}