[BOJ] 백준 2615번: 오목 _자바(JAVA)

1. 문제

https://www.acmicpc.net/problem/2615

 

---

2. 접근 및 해결

2-1) 접근

현재 도달한 배열의 좌표(i,j)를 기준으로 세로줄, 가로줄, 대각선, 역대각선을 만들어서 오목을 확인했습니다.

 

세로줄(ㅣ), 가로줄(ㅡ), 역대각선(\)에 대해 index 확인을 그림으로 나타내면 아래와 같습니다. 

백준 2615번 해설 세로줄, 가로줄, 역대각선

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 변경됩니다.

 

대각선에 대해서는 아래와 같습니다.

백준 2615번 해설 대각선

3. 대각선(/)

 list[i][j] -> list[i+1][j-1] -> list[i+2][j-2] ... 로 i는 +1, j는 -1 변경됩니다.

 

이런식으로 오목과 6목을 계산할겁니다.

 

2-2) 해결

주요 메소드는 2가지가 있습니다.

1. boolean checkFive(int color, int i, int j, int dx, int dy); // 오목 확인
2. boolean isNotSix (int color, int i, int j, int dx, int dy); // 6목 확인

 

1. checkFive 메소드

백준 2615번 해설 오목 확인 메소드

오목인지 확인하는 메소드입니다.

위에서 접근했던 방식대로 변경되는 값 만큼을 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 메소드

백준 2615번 해설 6목 확인 메소드

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)
    }
}

---

감사합니다!