2615 - 오목 (Java)

 

---

 

문제

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

 

풀이

모든 오목칸을 순회하면서 오목이 있는지 검사하면 된다.

 

단 신경써야하는 부분이 크게 두가지가 있다.

 

1. 오직 세로일때는 가장 위의 돌 출력, 그 외에는 좌측 돌 출력

 

이 조건에서 대각선인 경우에도 가장 왼쪽 돌을 출력해야한다.

 

오로지 세로로 일자로 오목일때만 가장 위의 돌을 출력하고, 그 외에는 다 왼쪽돌이다.

 

그리고 이 조건을 만족하기 위해서는 순회를  → ↓ 순서가 아니라

 

↓ → 순서로 순회하며 오목을 검사해야한다.

 

그래야지 세로일때는 가장 위의 오목돌에서 오목을 발견할 수 있고,

 

그 외에 대각선이나 가로일때도 왼쪽 돌부터 체킹하기 때문이다.

 

 

2. 6 목 검사

 

6목일 경우에는 취급하지 않는다.

 

6 목을 검사하기 위해서는 양쪽을 모두 체크해봐야한다.

 

0 0 0 0 0 0 0

0 1 1 1 1 1 1

0 0 0 0 0 0 0

 

위 경우에 [1,1] 의 1을 기준으로 검사하면 6목인게 자명하지만

 

[1,2] 로 오른쪽으로만 검사한다면 5목 조건에 들어맞을 수 있다.

 

그러니까 항상 반대쪽도 검사를 해서 6목이상인지 검사해야한다.

 

 

이 부분들만 조심한다음 좌우, 상하, 대각선을 기준으로 검사만 잘 하면 풀 수 있다.

 

코드

import java.util.*;
import java.io.*;

/**
 * [문제] (https://www.acmicpc.net/problem/2615)
 * 검은 바둑알 1, 흰 바둑알 2
 */

public class Main {


    public boolean search(List<List<Integer>> board, int x, int y) {

        int[] dx = new int[]{1, -1, 0, 0, 1, -1, 1, -1 };
        int[] dy = new int[]{0, 0, 1, -1, 1, -1, -1, 1 };
        int startX = x;
        int startY = y;
        int stone = board.get(x).get(y);

        // 탐색을 시작한다. 좌우세트로, 상하세트로, 대각세트로
        for (int i = 0; i < 8; i+=2) {
            int continuous = 1;

            while (true) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 범위에 속하며, 같은 돌일경우 진행한다.
                if (nx >= 0 && nx < 19 && ny >= 0 && ny < 19 && board.get(nx).get(ny) == stone) {
                    continuous++;
                    x = nx;
                    y = ny;
                    continue;
                }
                break;
            }

            x = startX;
            y = startY;

            while (true) {
                int nx = x + dx[i+1];
                int ny = y + dy[i+1];

                // 범위에 속하며, 같은 돌일경우 진행한다.
                if (nx >= 0 && nx < 19 && ny >= 0 && ny < 19 && board.get(nx).get(ny) == stone) {
                    continuous++;
                    x = nx;
                    y = ny;
                    continue;
                }
                break;
            }

            x = startX;
            y = startY;

            // 승자가 판가름 난 경우
            if (continuous == 5) {

                System.out.println(stone);
                System.out.println((startX+1) + " " + (startY+1));
                return true;
            }
        }

        return false;
    }

    public void solution() throws Exception {

        List<List<Integer>> board = new ArrayList<>();
        inputProcess(board);

        // 좌우상하 대각선 모두 검사를 한다.
        // 보드의 끝에 도달했을 때, 다음 칸이 같은 값이 아닐 경우 멈춘다
        // 멈춘후에 연속된 돌이 몇 개 인지 카운트 한 값을 보고 정답을 판단한다.
        for (int i = 0; i < 19; i++) {
            for (int j =0; j < 19; j++) {
                if (board.get(j).get(i) == 0) continue;
                if (search(board, j, i)) return;
            }
        }

        // 이긴 경우가 없으면 0 을 출력한다.
        System.out.println(0);
    }

    public void inputProcess(List<List<Integer>> board) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputLine;

        for (int i = 0; i < 19; i++) {
            inputLine = br.readLine();
            List<Integer> li = new ArrayList<>();

            String[] vals = inputLine.split(" ");
            for (String val : vals) {
                li.add(Integer.parseInt(val));
            }
            board.add(li);
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기

 

- 코드를 더 간결히 할 수 있을거 같긴한데 귀찮아서,,

 

- 생각보다 꼼꼼하게 검사해야해서 정답률이 낮았다.