Baekjoon 2615 오목 JAVA

2615번: 오목

문제

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.

입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

조건

[입력]

19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.

[출력]

첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.

풀이

해당 문제는 8방 탐색을 이용해서 쉽게 해결했다. 다만 문제를 제대로 읽지 않아 처음 틀려버렸다. 로직은 아래와 같은 방법으로 구현하였다.

1. 입력값을 2차원 배열에 입력한다.

2. map 배열을 탐색하면서 바둑돌일 경우 체크한다.

3. 체크에서는 오른쪽, 오른쪽 아래 대각선, 아래, 오른쪽 위대 각선 방향만 체크한다 (출력에서 젤 왼쪽 값만 출력)

4. 무한 반복하면서 같은 방향을 체크해서 카운트를 증가시킨다. 배열 범위 벗어나거나 바둑돌이 다를 때까지

5. 카운트가 5와 같다면 오목인 경우이지만 시작 좌표에서 반대방향을 체크해준다.

6. 반대방향 체크도 성공하면 바둑돌과 좌표를 출력한다.

코드

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

public class Main {

	static int map[][] = new int[19][19];
	static int[] 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));
		for (int i = 0; i < 19; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 19; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 0; i < 19; i++) {
			for (int j = 0; j < 19; j++) {
				if(map[i][j] != 0) // 바둑돌이면 체크함
					check(i,j);
			}
		}
		System.out.println(0);
	}
	private static void check(int y, int x) {
		for (int i = 0; i < 8; i = i + 2) { // 우, 우하대각선, 하, 우상대각선만 체크하면된다.
			int ny = y;
			int nx = x;
			int cnt = 1;
			while (true) {// 시작좌표에서 같은방향으로 계속 탐색
				ny = ny + dy[i];
				nx = nx + dx[i];
				if (ny < 0 || nx < 0 || ny >= 19 || nx >= 19 || map[ny][nx] != map[y][x]) { // 범위 벗어나거나 값다르면 멈춤
					break;
				}
				cnt++;
			}
			if (cnt == 5) { // 카운트가 5면 오목인경우임 이제 반대방향 하나의 값을 체크해줌
				int nyy = y + dy[i + 1]; // 시작좌표에서 반대방향
				int nxx = x + dx[i + 1]; // 시작좌표에서 반대방향
				if (nyy < 0 || nxx < 0 || nyy >= 19 || nxx >= 19 || map[nyy][nxx] != map[ny+dy[i+1]*5][nx+dx[i+1]*5]) { // 반대방향이 범위를 벗어나거나 값이 다르면 성공
					System.out.println(map[ny+dy[i+1]*5][nx+dx[i+1]*5]); // 해당 바둑돌 출력
					System.out.println((ny+dy[i+1]*5+1) + " " + (nx+dx[i+1]*5+1)); // 좌표출력해주는데 +1씩해줌 0,0으로 했기때문
					System.exit(0);
				}
			}
		}
	}
}

 

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