문제 탐색하기

입력 자료 정리

1. 19 x 19크기의 입력값이 주어지며, 0,1,2중 하나가 주어진다
2. 0은 그냥 빈칸이고 1과 2는 각각 사람이 둔 바둑알이다

해결방법 추론

1. 좌측 상단부터 시작해서 우측 하단까지 탐색하는 과정에서
   바둑알이 발견된다면 그 주위에 같은 바둑알이 있는지 확인하여
   총 5개의 바둑알 이 연속적으로 있다면 출력하도록 하는 방법을 생각했다
2. 이때 가장 왼쪽에 있는 바둑알이 처음 바둑알로 선택되도록 한다면
   탐색하는 방향을 줄일 수 있다
3. 하, 우하, 우, 우상으로만 탐색하면 된다
4. 오목에서는 6목이 나오거나 방향이 꺾이면 안된다.
   따라서 한쪽 방향으로만 이어서 탐색하도록 설계해야한다
5. 만약 한쪽방향으로 탐색했을 때,
   다섯 바둑알만이 연속적으로 이어져 있다면 바로 그 처음 위치를 출력하면 된다
6. 만약 모든 탐색에서도 조건을 만족시키지 않는다면 0을 출력하면 된다

시간복잡도 계산

1. 19 x 19 바둑판 안에서만 탐색이 진행된다.
2. 이때, 한쪽 방향으로 최대 5번만큼 탐색해서 오목인지를 판단한다
3. 따라서 총 시간복잡도는 O(19 x 19 x 5)이며,
   시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 19 x 19 크기의 int형 배열에 입력값을 관리한다
2. 탐색을 위한 배열을 하나 만들어 두며,
   방문배열 역할과, 방향정보도 가지고 있는 19 x 19 x 4 크기의
   int형 배열을 만든다

탐색 설계

1. 19 x 19크기의 배열을 탐색하며, 만약 해당 배열이 0이 아니라면
   오목 여부를 탐색한다
2. 4방향에 대해서 탐색하며, 해당 방향이 미방문했다는 0이며,
   검증 결과가 5인 경우 해당 위치의 값을 출력한다

검증 설계

1. 현재 방향으로 탐색했을 때,
   같은 오목알이 있다면 탐색을 시작한 배열에 그 숫자를 누적하여 더해주고
   그 값을 리턴한다
2. 재귀함수로 탐색을 이어나가며, 만약 재귀함수가 이어지지 않을 경우
   1로 리턴하여 방문체크와 함께, 이전 검증이 다음 검증에 이어지지
   않도록 한다

출력값 설계

1. 검증 결과 오목이고 방문하지 않았다면 시작지점에 대한
   바둑알 번호를 출력하고, 그 위치의 x값과 y값을 출력하면 정답이 된다.

정답코드

(1회차 시도 성공!)

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

public class Main {

    static int[][] arr = new int[21][21];
    static int[][][] memo = new int[21][21][4];
    static int[] dx = { 1, 1, 0, -1 };
    static int[] dy = { 0, 1, 1, 1 };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int i = 1; i <= 19; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= 19; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        bw.write(finds());

        br.close();
        bw.close();
    }

    private static String finds() {
        for (int i = 1; i <= 19; i++) {
            for (int j = 1; j <= 19; j++) {
                if(arr[j][i] != 0){
                    for (int k = 0; k < 4; k++) {
                        if(memo[j][i][k] == 0 && chk(j,i,k, arr[j][i]) == 5){
                            return arr[j][i] + "\n" + j + " " + i + "\n";
                        }
                    }
                }
            }
        }
        return "0";
    }

    private static int chk(int x, int y, int d, int type) {
        int nx = x + dx[d];
        int ny = y + dy[d];

        if(arr[nx][ny] == type){
            return memo[nx][ny][d] = chk(nx,ny,d,type) + 1;
        }

        return 1;
    }

}

문제 링크

2615 - 오목