[알고리즘] SWEA 11315 : 오목 판정 - JAVA

문제 설명

N X N 크기의 판이 있다. 판의 각 칸에는 돌이 있거나 없을 수 있다. 돌이 가로, 세로, 대각선 중 하나의 방향으로 다섯 개 이상 연속한 부분이 있는지 없는지 판정하는 프로그램을 작성하라.

  

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(5 ≤ N ≤ 20)이 주어진다.

다음 N개의 줄의 각 줄에는 길이 N인 문자열이 주어진다. 각 문자는 ‘o’또는 ‘.’으로, ‘o’는 돌이 있는 칸을 의미하고, ‘.’는 돌이 없는 칸을 의미한다.

  

출력

각 테스트 케이스 마다 돌이 다섯 개 이상 연속한 부분이 있으면 “YES”를, 아니면 “NO”를 출력한다.

 

풀이

맵을 탐색하며 'o'를 만나면 5개가 이어져있는지 체크하면 되는 문제였습니다.처음엔 8개의 방향을 모두 확인하였다가 처음 o를 만나기 위해 탐색할때 왼쪽위에서 부터 오른쪽 아래로 가기 때문에 왼쪽 아래 대각선, 아래, 오른쪽 아래 대각선, 오른쪽 4방향만 검사해도 되었습니다.

 

소스코드

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

public class Solution {
	static char[][] map = new char[20][20];
	static int[] dx = {0,1,1,1};
	static int[] dy = {1,1,0,-1};
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		for(int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			
            	// 맵 입력
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				String line = st.nextToken();
				for(int j = 0; j < N; j++) {
					map[i][j] = line.charAt(j);
				}
			}
			
			boolean isFive = false;
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(map[i][j] == 'o') {
						isFive = fiveCheck(i, j);
					}
					if(isFive)break;
				}
				if(isFive)break;
			}
			
			if(isFive)System.out.println("#"+tc+" "+"YES");
			else System.out.println("#"+tc+" "+"NO");
		}

	}
	
	public static boolean fiveCheck(int x, int y) {
		for(int k = 0; k < 4; k++) {
			for(int cnt = 1; cnt < 5; cnt++) {
				int nx = x + dx[k] * cnt;
				int ny = y + dy[k] * cnt;
				
				if(nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 'o') {
				// 처음 찾은 'o' 제외하고 4개 찾으면 종료
                   		if(cnt == 4)return true;
				}
				else break;
			}
		}
		
		return false;
	}

}