(Java/자바) - 백준(BOJ) 2615번 : 오목

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

2615번: 오목

---

• 문제 : 

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

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

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

 

 

 

---

• 풀이 :

브루트포스 문제입니다.

모든 좌표에 대해 (가로), (세로), (왼쪽대각선), (오른쪽대각선) 총 4가지 경우에서 같은 색인 바둑알의 개수가 5개일 때 가장 왼쪽 위 좌표를 출력하면 됩니다.

 

풀이입니다.

 

1. 이중 for문으로 0 ~ 18까지 모든 좌표를 탐색합니다. 이 때, (i,j)에 바둑알이 놓여있다면 위에서 언급한 4가지 경우를 확인합니다.

 

2. d 배열을 사용하여 4가지 방향을 지정해주었고 양방향으로 연결되어 있는 경우가 있기 때문에 한 번은 d의 값을 더하고 한 번은 d의 값을 빼주는 방식으로 탐색했습니다.

 

3. 연결되어 있는 같은 색의 바둑알이 5개일 경우 그 때의 i,j를 출력하고 종료합니다. 이중 for문의 탐색 순서를 j 증가 -> i 증가의 순서로 지정했기 때문에 항상 가장 왼쪽 위의 좌표가 출력되게 됩니다.  

 

 

 

---

• 소스코드 : 

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

public class Main{
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[][] board = new char[19][19];
		int [][] d = {{0,1}, {1,0}, {1,1}, {-1,1}};
		
		//		board 입력받기
		for (int i = 0; i < 19; i++) {
			String input = br.readLine();
			for (int j = 0, index = 0; j < 19; index += 2, j++) {
				board[i][j] = input.charAt(index);
			}
		}
		
		
		// 모든 칸에 대해 오목 완성 찾기		
		for (int j = 0; j < 19; j++) {
			for (int i = 0; i < 19; i++) {
				if (board[i][j] == '1' || board[i][j] == '2') {
					for (int k = 0; k < 4; k++) {
						int ax = i; // x좌표
						int ay = j; // y좌표
						int cnt = 1; // 일치하는 바둑알의 개수
						
						// 증가하는 방향 탐색
						while (true) {
							ax += d[k][0];
							ay += d[k][1];
							if ( 0 <= ax && ax < 19 && 0 <= ay && ay < 19) {
								if(board[i][j] == board[ax][ay])cnt ++;
								else {
									break;
								}
							} else break;
						}
						ax = i;
						ay = j;
						
						// 증가하는 방향의 반대방향 탐색
						while( true) {
							ax -= d[k][0];
							ay -= d[k][1];
							if ( 0 <= ax && ax < 19 && 0 <= ay && ay < 19) {
								if(board[i][j] == board[ax][ay])cnt ++;
								else break;

							} else break;
						}
						
						// 같은 오목눈이 5개라면
						if (cnt == 5) {
							System.out.println(board[i][j]);
							System.out.println((i+1) + " " + (j+1));
							return;
						}
						
					}
				}
			}
		}
		
//		아무도 이기지 않았을 경우
		System.out.println(0); 	
		
		
	}	
}