[자바] 백준 2072 - 오목 (java)

 문제 : boj2072

---

 

필요 알고리즘 개념

• 구현, 시뮬레이션
  
  • 문제에 제시된대로 시뮬레이션을 구현해주면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  문제에 제시된대로 구현만 해주면 되는 문제이다. 19x19 짜리 오목판이므로 배열을 두고, 흑과 백에 각각 특정 값을 주고 순서대로 배열에 넣어주면 된다. 그리고 넣어준 값을 기준으로 5개가 연속되도록 넣여져 있는지 확인해주면 된다.

 

  구현 자체가 어려울수도 있으므로 내 방식을 설명하면 아래와 같다.

1. 우선 승부가 날 수 있는건 적어도 9게임부터이다. 따라서 N이 8이하라면 -1을 출력해준다. 그리고 8번까지는 오목을 체크하지 않고 바로바로 배열에 넣어준다. (내 경우엔 흑은 1, 백은 2를 사용했다.)

 

2. 9번째 경기부터는 승부가 날 수 있으므로 매번 흑 혹은 백을 넣을때마다 해당 지점을 중심으로 8방향을 확인해 5개가 모였는지 확인해줬다. 데이터양이 작아서 사실 매번 전체 바둑판을 다 체크해도 상관은 없다.

 

3. '2'에서 오목인지 체크하는건 is5mok() 함수이다. 8방향에 대해 배열 DR,DC에 0,1은 좌우 / 2,3은 상하.. 이런식으로 서로 엇갈리게 배치하고 4칸의 배열에 순서대로 0,1 인덱스 / 2,3 인덱스 / 4,5 인덱스 / 6,7인덱스를 세주었다. 따라서 최종적으로 cnt배열 4칸은 가로로 오목인지, 세로로 오목인지, \ 대각선으로 오목인지, / 대각선으로 오목인지를 나타낸다. 정확히 5개 일 때만 오목인걸 주의해야 한다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

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

    public void solution() throws Exception {
        int[][] arr = new int[20][20];
        int n = Integer.parseInt(br.readLine());
        if (n < 9) {
            System.out.println(-1);
            return;
        }
        for (int i = 0; i < 8; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = i%2 + 1;
        }

        for (int i = 8; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = i%2 + 1;
            if (is5mok(arr, a, b, i%2 + 1)) {
                System.out.println(i+1);
                return;
            }
        }
        System.out.println(-1);
    }

    private static final int[] DR = {0, 0, -1, 1, -1, 1, -1, 1};
    private static final int[] DC = {1, -1, 0, 0, -1, 1, 1, -1};
    private boolean is5mok(int[][] arr, int r, int c, int color) {
        int[] cnt = new int[4];
        Arrays.fill(cnt, 1);
        for (int d = 0; d < 8; d++) {
            for (int a = r+DR[d], b = c+DC[d]; a>=0 && a<arr.length && b>=0 && b<arr[0].length && arr[a][b] == color; a+=DR[d], b+=DC[d]) {
                cnt[d/2]++;
            }
        }
        for (int i = 0; i < 4; i++) {
            if (cnt[i] == 5)
                return true;
        }
        return false;
    }
}