[BOJ] 2615. 오목 - JAVA

🔗 문제

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

2615번: 오목

 

💻 풀이 및 코드

문제 유형 : 구현, 브루트 포스

 

바둑돌이 연속으로 5개 놓인 바둑돌의 색과 위치를 출력하는 문제

 

 

풀이

 

• 완탐이므로 모든 위치에서 차례대로 바둑돌이 5개가 연속으로 놓이는지 체크한다.

• 왼쪽에서 오른쪽으로, 위에서 아래로 순서로 탐색을 진행하기 때문에 { 오른쪽, 오른쪽 아래 대각선, 아래, 왼쪽 아래 대각선 } 방향 총 4방향만 탐색하면 된다. (다른 방향들은 이미 위에서 체크하며 내려왔다.)

static int[] du = { 0, 1, 1, 1 };
static int[] dv = { 1, 1, 0, -1 };

• 단, 문제에서 5개의 바둑돌 중 가장 왼쪽, 그 중 가장 위의 바둑돌의 위치를 출력하라고 했기 때문에 왼쪽 아래 대각선 방향 (d==3) 이 정답일 경우 시작점이 아닌 가장 마지막에 놓인 바둑돌을 출력해야 한다.

if(cnt == 5) {
    if(d==3) {
        nu = u; nv = v;
        for(int i=0; i<4; i++) {
            nu += du[d];
            nv += dv[d];
        }

        ans[0] = nu+1;
        ans[1] = nv+1;
    }
    ...
}

 

• 추가로 주의할 점은 갯수를 세기 진행한 방향의 반대 방향도 바둑돌의 갯수를 고려해야 한다는 것이다. (처음에 이 부분때문에 틀렸다.)
• 예를 들어, 오른쪽 방향으로 바둑돌의 갯수가 5개인지 탐색했다면 왼쪽 방향으로도 탐색해야 한다.
• 다음과 같이 6개의 바둑돌이 일렬로 놓여져 있다고 가정하자. 1번 위치에서 오른쪽 방향으로 돌의 갯수를 센다면 6개이기 때문에 답이 될 수 없다.

• 다음 2번 위치에서 오른쪽으로만 탐색한다면 바둑돌의 갯수가 5개 이기 때문에 오답을 출력하게 된다. 따라서 시작점의 반대 방향에 놓인 바둑돌의 갯수도 고려해야 한다.

// 증가하는 방향 탐색
while(true) {
    nu += du[d];
    nv += dv[d];

    if(nu<0 || nu>=N || nv<0 || nv>=N || map[nu][nv] != map[u][v]) break;
    if(++cnt > 5) break;
}

// 반대 방향 탐색
nu = u; nv = v;
while(true) {
    nu -= du[d];
    nv -= dv[d];

    if(nu<0 || nu>=N || nv<0 || nv>=N || map[nu][nv] != map[u][v]) break;
    if(++cnt > 5) break;
}

if(cnt == 5) {
    ...
    return true;
}

 

나머진 코드를 보면 이해가 갈 것 같다.

 

 

느낀 점

29번 시도 끝에 드디어 맞았다. 사실 너무 틀려서 다른 사람 코드로 맞고 내 코드가 어디가 잘못됐는지 안찾고 넘어가려다가 자꾸 마음에 걸려서 3일 후에 다시 풀어봤다. 반대방향으로 왜 탐색하는지 이해가 안갔고, check(i, j) 에서 cnt > 5 일 경우 바로 return false 를 한 게 문제였다. break 로 수정하니 맞았다. 다시 풀어보길 잘한 것 같다.

 

전체 코드

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

public class Main_bj_2615_오목 {

	static int N = 19;
	static int[][] map;
	static int[] ans;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_2615.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		map = new int[N][N];
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		ans = new int[2];
		boolean ok = false;
		outer: for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0)
					continue;
				if(check(i, j)) {
					System.out.println(map[i][j]);
					System.out.println(ans[0] + " " + ans[1]);
					ok = true;
					break outer;
				}
			}
		}
		
		if(!ok)
			System.out.println(0);
		br.close();
	}

	static int[] du = { 0, 1, 1, 1 };
	static int[] dv = { 1, 1, 0, -1 };
	
	static boolean check(int u, int v) {
		int nu=0, nv=0;
		for(int d=0; d<4; d++) {
			nu = u; nv = v;
			
			int cnt = 1;
			
			// 증가하는 방향 탐색
			while(true) {
				nu += du[d];
				nv += dv[d];
				
				if(nu<0 || nu>=N || nv<0 || nv>=N || map[nu][nv] != map[u][v]) break;
				if(++cnt > 5) break;
			}
			
			// 반대 방향 탐색
			nu = u; nv = v;
			while(true) {
				nu -= du[d];
				nv -= dv[d];
				
				if(nu<0 || nu>=N || nv<0 || nv>=N || map[nu][nv] != map[u][v]) break;
				if(++cnt > 5) break;
			}
			
			if(cnt == 5) {
				if(d==3) {
					nu = u; nv = v;
					for(int i=0; i<4; i++) {
						nu += du[d];
						nv += dv[d];
					}
					
					ans[0] = nu+1;
					ans[1] = nv+1;
				}
				else  {
					ans[0] = u+1;
					ans[1] = v+1;
				}
				
				return true;
			}
			
		}
		
		return false;
	}

}