Baekjoon 2072 오목 JAVA

2072번: 오목

문제

19x19 크기의 바둑판에, 돌을 놓을 좌표가 주어지면 이 게임이 몇수만에 끝나는 지를 알아보려고 한다. 사용하고자 하는 바둑판의 모양은 위의 그림과 같으며, (1, 1)이 가장 왼쪽 위의 좌표이고 (19, 19)가 가장 오른쪽 아래의 좌표이다. 오목은 흑 또는 백이 5개의 돌을 가로, 세로, 혹은 대각선으로 연속으로 놓았을 경우 게임이 끝나게 된다. 즉, 다음 그림과 같은 경우를 말한다.

게임은 흑이 먼저 시작하며, 한수씩 서로 번갈아 가며 두게 된다. 다음 좌표들과 같이 차례로 돌을 놓으며 게임을 진행한다고 하자. (홀수번째는 흑, 짝수번째는 백)

• 1 - (3,3)
• 2 - (2,3)
• 3 - (3,4)
• 4 -  (2,2)
• 5 - (3,2)
• 6 - (3,1)
• 7 - (3,5)
• 8 - (2,4)
• 9 - (2,5)
• 10 - (2,1)
• 11 - (1,5)
• 12 - (4,1)
• 13 - (4,5)
• 14 - (5,5)
• 15 - (1,4)
• 16 - (5,1)
• 17 - (1,3)
• 18 - (1,1)
• 19 - (5,3)
• 20 - (5,2)
• 21 - (1,2)
• 22 - (5,4)
• 23 - (4,2)
• 24 - (4,4)
• 25 - (4,3)

위의 순서대로 바둑판에 돌을 놓으면 아래의 왼쪽 그림과 같이 된다.

그런데 생각해보면, 위의 좌표대로 돌을 놓았을 때 오른쪽 그림처럼 18번째의 돌을 놓는 것으로서 게임이 끝나 버리는 것을 알 수 있다. 이 경우, 답은 18이다.

바둑판에 돌을 놓는 좌표가 입력될 때, 몇 번째 수에서 오목이 끝나는지를 찾는 프로그램을 작성하시오. 오목을 두다 보면 다음과 같이 돌이 5개를 거치지 않고 6개 이상의 돌이 나란히 놓이는 경우가 발생할 수 있다. 이런 경우에는 승리를 인정하지 않고 오목이 계속된다는 것에 주의하라.

 

조건

[입력]

첫째 줄에 바둑판에 놓이는 돌의 개수 N(1 ≤ N ≤ 100)이 주어진다. 그다음 N 줄에는 놓이는 돌의 좌표들이 차례로 주어진다. (홀수번째는 흑, 짝수번째는 백) 돌을 놓은 곳에 또 돌을 놓는 경우는 없다.

 

[출력]

첫째 줄에 몇 번째 수에서 승패가 갈리는지를 출력한다. 승패가 갈리지 않는 경우에는 -1을 출력한다.

 

풀이

해당 문제는 오목을 두는 위치가 주어졌을 때 몇 번째 수에 오목이 되는지를 구하는 문제다.

기존에 오목 문제를 몇 문제 풀어보았는데 해당 문제처럼 오목을 두면서 체크하는 경우는 처음이라 한번 풀어보게 되었다.

시키는 조건에 맞도록 구현하는 문제였고 로직은 아래와 같은 방식으로 구현하였다.

 

1. 입력값을 입력받는다. 이때 좌표값을 -1 해준다 문제는 1,1에서 시작 나는 0,0에서 시작

2. 입력값을 입력받는 동시에 오목이 성립하는지 체크한다 단 오목이 10수 이상 두어졌을 때

    2-1. 8방 탐색을 진행하는데 두 방향 즉 일직선이 되는 양 방향을 체크하여준다.

        ex) 오른쪽을 모두 체크하고 나면 왼쪽을 체크한다.

    2-2. 먼저 체크 한 방향에 이상이 없으면 반대 방향을 체크한다.

    2-3. 모두 체크한 후 cnt가 5라면 오목인 경우다 리턴해준다.

3. 출력한다.

 

코드

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

public class Main {

	static int ans, map[][], dy[]= {0, 0, 1, -1, 1, -1, -1, 1 }, dx[]= {1, -1, 1, -1, 0, 0, 1, -1}; //우 좌 우하대각선, 좌상대각선, 하,상, 우상대각선,좌하대각선
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		map = new int[19][19];
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()); // 입력 좌표값 시작이 1,1 이니깐 -1해줌
			int y = Integer.parseInt(st.nextToken())-1;
			int x = Integer.parseInt(st.nextToken())-1;
			if(i % 2 == 1)
				map[y][x] = 1; // 흑
			else
				map[y][x] = 2; // 백
			if(i >= 10 && check(y,x)) { // 적어도 돌이 10개이상이여야 오목이 가능
				ans = i;
				break;
			}
		}
		ans = ans == 0 ? -1 : ans;
		System.out.println(ans);
	}
	
	private static boolean check(int y, int x) {
		for (int i = 0; i < 8; i=i+2) { // 8방탐색을 할껀데 한번에 두방향 즉 1직선되는 양방향을 체크함
			int cnt = 1;
			int ny = y;
			int nx = x;
			while(true) { // 한쪽을 먼저 체크함
				ny += dy[i];
				nx += dx[i];
				if(ny < 0 || nx < 0 || ny >= 19 || nx >= 19 || map[ny][nx] != map[y][x] || cnt > 5) // 배열 범위 벗어나거나 돌이다르거나 카운트가 5보다 큰경우
					break;
				cnt++;
			}
			int py = y;
			int px = x;
			while(true) { // 체크한쪽 반대 방향을 체크함
				py += dy[i+1];
				px += dx[i+1];
				if(py < 0 || px < 0 || py >= 19 || px >= 19 || map[py][px] != map[y][x] || cnt > 5) // 배열 범위 벗어나거나 돌이다르거나 카운트가 5보다 큰경우
					break;
				cnt++;
			}
			if(cnt == 5) // 오목인경우
				return true;
		}
		return false;
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드