[백준2615] 오목 - 자바(JAVA)

1. 문제

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

2615번: 오목

2. 풀이

문제에서 주의할 내용은 다음과 같습니다.

1. 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
2. 가장 왼쪽에 있는 바둑알의 가로줄 번호와, 세로줄 번호를 순서대로 출력

• 저는 가장 왼쪽에 있는 바둑알을 출력해야하기 때문에 map[row][col] 에서 열->행 순서로 탐색을 했습니다.
  • EX) map[0][0] map[1][0] map[2][0] map[3][0]... map[0][1] map[1][1] map[2][1] map [3][1] ... map[0][2] map[1][2] map[2][2] map[3][2]... map[0][19] map[1][19] map[2][19] map [3][19] 
• map[row][col]에 바둑알이 있을 때 가로, 세로, 대각선 아래, 대각선 위  방향으로 탐색하면서 같은 바둑알의 갯수를 세었습니다.
• 여기서 boolean 배열 visit을 두어서 각 방향으로 이미 탐색한 곳을 표시해두어서 반복해서 탐색하지 않도록 백트래킹을 적용했습니다.

3. 코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int[][] map = new int[19][19];
		boolean[][] visit_r = new boolean[19][19];
		boolean[][] visit_c = new boolean[19][19];
		boolean[][] visit_rc = new boolean[19][19];
		boolean[][] visit_rcr = new boolean[19][19];

		for (int i = 0; i < 19; i++) {
			String[] input = br.readLine().split(" ");
			for (int j = 0; j < 19; j++) {
				map[i][j] = Integer.parseInt(input[j]);
				if (map[i][j] > 0) {
					visit_r[i][j] = true;
					visit_c[i][j] = true;
					visit_rc[i][j] = true;
					visit_rcr[i][j] = true;
					;
				}
			}
		}

		for (int j = 0; j < 19; j++) {
			for (int i = 0; i < 19; i++) {
				if (map[i][j] > 0) { // 탐색
					// 가로
					if (visit_c[i][j]) {
						int cnt = 0;
						boolean flag = true;
						while (flag) {
							if (j + cnt >= 19) {
								flag = false;
							} else if (map[i][j + cnt] == map[i][j]) {
								visit_c[i][j + cnt] = false;
								cnt++;
							} else {
								flag = false;
							}
						}
						if (cnt == 5) {
							System.out.println(map[i][j]);
							System.out.printf("%d %d", i + 1, j + 1);
							return;
						}
					}

					// 세로
					if (visit_r[i][j]) {
						int cnt = 0;
						boolean flag = true;
						while (flag) {
							if (i + cnt >= 19) {
								flag = false;
							} else if (map[i + cnt][j] == map[i][j]) {
								visit_r[i + cnt][j] = false;
								cnt++;
							} else {
								flag = false;
							}
						}
						if (cnt == 5) {
							System.out.println(map[i][j]);
							System.out.printf("%d %d", i + 1, j + 1);
							return;
						}
					}

					// 대각선 아래로
					if (visit_rc[i][j]) {
						int cnt = 0;
						boolean flag = true;
						while (flag) {
							if (i + cnt >= 19 || j + cnt >= 19) {
								flag = false;
							} else if (map[i + cnt][j + cnt] == map[i][j]) {
								visit_rc[i + cnt][j + cnt] = false;
								cnt++;
							} else {
								flag = false;
							}
						}
						if (cnt == 5) {
							System.out.println(map[i][j]);
							System.out.printf("%d %d", i + 1, j + 1);
							return;
						}
					}

					// 대각선 위로
					if (visit_rcr[i][j]) {
						int cnt = 0;
						boolean flag = true;
						while (flag) {
							if (i - cnt < 0 || j + cnt >= 19) {
								flag = false;
							} else if (map[i - cnt][j + cnt] == map[i][j]) {
								visit_rcr[i - cnt][j + cnt] = false;
								cnt++;
							} else {
								flag = false;
							}
						}
						if (cnt == 5) {
							System.out.println(map[i][j]);
							System.out.printf("%d %d", i + 1, j + 1);
							return;
						}
					}
				}
			}
		}
		System.out.println(0);

	}
}