백준 2615 번: 오목 (java)

문제

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

2615번: 오목

 

난이도 : 실버1

유형 : 구현, 브루트포스 알고리즘

 

접근법

 

-변수

map[][] : 입력데이터

memo[][][] : x 좌표, y 좌표, d 탐색방향 (4방향

int[] dx = {1, 1, 0, -1}; 

int[] dy = {0, 1, 1, 1};

    -> dx, dy : x,y 탐색방향 인덱스

 

19x19의 타일을 전체 탐색하여 오목을 찾아 내야한다. 오목이 가능한 경우는 수평, 수직, 우측대각, 좌측대각 4개의 경우가 존재한다. 그렇기에 [19][19][4] 의 크기를 가지는 memo변수를 선언하였다.

최악의 경우(오목이 없는경우) 19x19x4번의 탐색을 진행한다.

 

먼저 calc 라는 함수는 정수를 반환하고 있고 5를 반환하면 정답을 출력하는것을 알 수있다.

if(memo[i][j][d] ==0 &&  calc(i,j,d,map[i][j]) == 5){
	return map[i][j] + "\n" + i + " " + j + "\n";
}

 

calc 함수를 라인별로 살펴보면

calc(x, y, dir, color){ // 이전 x, y, color 값, 이번반복에서 탐색할 방향변수 dir
  nx = x+dx[dir]; //현재 위치에서 방향변수 x 적용
  ny = y+dy[dir]; //현재 위치에서 방향변수 y 적용

  if(map[nx][ny] == color){ //탐색 방향이 이전 color 값과 같다면
    return memo[nx][ny][dir] = calc(nx, ny, dir, color) +1;  //calc 를 재귀호출하고 +1한다. calc 호출시 현재 dir 방향으로 계속해서 탐색을 이어간다.
  }
  return 1;
}

 

 

아래 그림의 상단에 1 ->2 로 향하는 4방향을 dx, dy 변수로 탐색을한다.

calc 함수의 이전 color == 현재 컬러 일치(연속으로 돌이 놓아져 있다면) 해당 방향으로 계속해서 돌의 색이 일치하는지 재귀호출을 통해 비교를 하고 일치하지 않는다면 일치한 횟수만큼의 수를 반환한다.

 

 

 

 

풀이

 

import java.io.*;
import java.util.*;
public class Main {
    static int[][] map = 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 bf = new BufferedReader(new InputStreamReader(System.in));
        int input[][] = new int[19][19];
        for(int i= 1; i<=19; i++){
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for(int j=1; j<=19; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(findOmok());

    }
    private static String findOmok(){
        for(int j=1; j<=19; j++){
            for(int i=1; i<=19; i++){
                if(map[i][j] !=0){
                    for (int d=0; d<4; d++){
                        if(memo[i][j][d] ==0 &&  calc(i,j,d,map[i][j]) == 5){
                            return map[i][j] + "\n" + i + " " + j + "\n";
                        }
                    }
                }
            }
        }

        return "0";
    }

    private static int calc(int x, int y, int dir, int color){
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(map[nx][ny] == color){ //다음 우측 대각, 좌측 대각, 수평, 수직이 같다면 계속 재귀호출을 한다.
            return memo[nx][ny][dir] = calc(nx, ny, dir, color) +1; //
        }
        return 1;
    }

}

 

 

재귀를 사용하지 않는다는 조건이 있다면, 이중 반복문에 각 방향의 케이스를 각자 비교하는 방법도 사용 할 수있겠다.

for(int i=0; i<19;i++){

    for(int j=0; j<19;j++){

        case_수평;

        case_수직;

        case_우대각;

        case_좌대각;

    }

}