[java]오목 - 백준2615

문제



풀이

문제 해석을 하자면,

  • 바둑판에 바둑알을 입력으로 주어지면 “오목게임” 결과를 구하라.


풀이

  • 방향을 4가지로 생각해야한다. -> 오른쪽, 대각선 아래, 아래, 대각선 위
    • 이를 통해서 정답좌표도 바로 구할 수 있다.
  • 그리고 “육목”인지 판단이 중요하다.
    • 오목 시작점과 끝쪽에 “바둑알 더 있나 확인”
  • 반례조심 : 현재 6목일때 좌표 한칸 이동후에 다시 확인할때 5목으로 판별나서 문제가 발생



코드

public static int[][] inArr = new int[22][22];
public static Pair[] outArr = new Pair[10];
public static int[] dx = {0,1,1,-1}; // 오른쪽, 대각선 아래, 아래, 대각선 위
public static int[] dy = {1,1,0,1};
public static int[] rdx = {0,-1,-1,1}; // reverse
public static int[] rdy = {-1,-1,0,-1};
public static int result, ansX, ansY;
public static int N = 19;
public static boolean endCheck = false;

public static void dfs(int depth, int dir, int cx, int cy) {
    //base condition
    if(depth == 4) {
        // 육목인지만 추가 판단후 "오목확정" 지으면 된다. -> 끝과 처음쪽 둘다 바둑알 더 있나 확인
        int nx = cx+dx[dir];
        int ny = cy+dy[dir];
        int px = outArr[0].x+rdx[dir];
        int py = outArr[0].y+rdy[dir];
        int nxtCheck = 0;
        int preCheck = 0;
        if(nx<0||ny<0||nx>=N||ny>=N) {
            nxtCheck = 1;
        }
        if(px<0||py<0||px>=N||py>=N) {
            preCheck = 1;
        }
        if(nxtCheck == 1 && preCheck == 1) {
            // 앞, 뒤 둘다 범위 초과라 "오목"확정
            result = outArr[depth].val; // 해당 바둑색깔 기록
            endCheck=true;
        }
        if(nxtCheck == 0) {
            // 뒤가 범위 초과 아닐때, 육목인지 체크
            if(inArr[nx][ny]==outArr[depth].val) {
                result = 0; endCheck = false;
                return; // 이미 "육목"이라 가망없음
            }else {
                result = outArr[depth].val; // 해당 바둑색깔 기록
                endCheck = true;
            }
        }
        if(preCheck == 0) {
            // 앞이 범위 초과 아닐때, 육목인지 체크
            if(inArr[px][py]==outArr[depth].val) {
                result = 0; endCheck = false;
                return; // 이미 "육목"이라 가망없음
            }else {
                result = outArr[depth].val; // 해당 바둑색깔 기록
                endCheck = true;
            }
        }
        return;
    }
    //recursion
    int nx = cx+dx[dir];
    int ny = cy+dy[dir];
    if(nx<0||ny<0||nx>=N||ny>=N) return;
    if(outArr[depth].val == 0) return;
    if(outArr[depth].val != inArr[nx][ny]) return;
    outArr[depth+1]=new Pair(nx,ny,inArr[nx][ny]);
    dfs(depth+1, dir, nx, ny);
}

public static void main(String[] args) throws Exception {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //input
    for(int i=0; i<N; i++) {
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++) {
            inArr[i][j] = Integer.parseInt(stk.nextToken());
        }
    }
    //run
    loop: for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(inArr[i][j]==0) continue;
            outArr[0] = new Pair(i,j,inArr[i][j]);
            for(int k=0; k<4; k++) {
                dfs(0, k, i, j);
                if(endCheck) {
                    ansX = i; ansY = j; break; // 4방향의 첫 시작점이 정답좌표
                }
            }
            if(endCheck) break loop;
        }
    }
    //output
    if(result != 0)
        sb.append(result).append("\n").append(ansX+1).append(" ").append(ansY+1);
    else
        sb.append(result).append("\n");
    System.out.print(sb);
}

static class Pair {
    int x; int y; int val;
    public Pair(int x, int y, int val) {
        this.x=x; this.y=y; this.val=val;
    }
}



느낀점

재귀가 아닌 for문으로 풀었으면 더 간단했을것 같다..

여러 반례들 추가

/*
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0
0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1
7 3


0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1
4 3


0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0
0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 2 1 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2

0
*/

댓글남기기

참고