[알고리즘] 2615. 오목

0. 문제

 

2615번: 오목

 

---

1. 문제 이해

 

1. 4가지 방향으로 같은 색의 돌을 센다.
2. 단, 같은 방향이면 한 번만 센다.
3. 돌이 5개 있으면 …
   1. 가장 왼쪽에 있는 돌을 출력.
   2. 세로로 돌이 위치하면 가장 위에 있는 돌 출력.

 

---

2. 제출

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

public class Main {

	public static int[][] board = new int[19][19];
	public static int winner=0, yy=20, xx=20;
	public static int[] dy = {0, 1, 1, 1};
	public static int[] dx = {1, 1, 0, -1};
	
	public static void find(int y, int x) {
		for(int dir=0; dir<4; dir++) {
			int cnt=1;
			
			// 이미 한번 탐색했던적 있다면 넘어간다.
			int by = y + dy[dir] * -1;
			int bx = x + dx[dir] * -1;
			boolean underflow = by < 0 || bx < 0;
			boolean overflow = by >= 19 || bx >= 19;
			if(!underflow && !overflow && board[y][x] == board[by][bx]) continue;
			
			for(int i=1; i<19; i++) {
				int ny = y + dy[dir] * i;
				int nx = x + dx[dir] * i;
				
				// 장외인지 확인
				boolean underflow1 = ny < 0 || nx < 0;
				boolean overflow1 = ny >= 19 || nx >= 19;
				if(underflow1 || overflow1) break;

				// 같은 돌 색이 몇 번 이어지는지 확인
				if(board[y][x] != board[ny][nx]) break;
				cnt++;
			}
			if(cnt==5) {
				winner = board[y][x];
				yy=y;
				xx=x;
				if(dir==3) { // 주의 : 왼쪽 아래에서 오른쪽 위로 올라가는 방향일 때 가장 왼쪽 돌 선택
					yy+=4;
					xx-=4;
				}
				return;
			}
		}
	}
	
	// 모든 돌 확인	
	public static void solve() {
		for(int y=0; y<19; y++) {
			for(int x=0; x<19; x++) {
				if(board[y][x]==0)continue;
				find(y, x);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		for(int y=0; y<19; y++) {
			st = new StringTokenizer(br.readLine());
			for(int x=0; x<19; x++) {
				board[y][x] = Integer.parseInt(st.nextToken());
			}
		}
		solve();
		System.out.println(winner);
		if(winner!=0) { // 무승부가 아니라면
			System.out.println((yy+1) + " " +(xx+1));
		}
	} 
	
}

 

처음에 구현의 방향성을 잡기 어려웠고 반례가 많은 문제다.

 

잊을만하면 다시 풀어보자.

 

---