[Problem Solving] SWEA_11315. 오목 판정

🧐 문제 분석

N * N 크기의 오목판
돌이 가로, 세로, 대각선 중 하나의 방향으로 다섯 개 이상 연속한 부분이 있는지 없는지 판정
. : 돌이 없음
o : 돌이 있음

0. 문제 접근 방법

• 완전 탐색 (Brute Force)
• 각 칸을 기준으로 연속된 5개 이상의 돌이 있는지 검사 & 탐색

1. 입력

// 입력
1
5
....o
...o.
..o..
.o...
o....

• T: 테스트 케이스
• N : 오목판의 크기 (가로 칸 수 / 세로 칸 수)
• N * N의 오목판의 입력값

2. 로직

1) 4가지 방향 벡터 정의

➡️ ⬇️ ↘️ ↙️

int[] dx = {0, 1, 1, 1};
int[] dy = {1, 0, 1, -1};

2) 판별 로직

• 모든 좌표 (x, y) 탐색
• 돌이 있는 칸이라면 그 칸을 기준으로 각 4방향의 최소 4칸 탐색
• 플래그 & 카운팅 변수: 이동한 좌표값이 돌인지 & 돌이라면 카운팅
• 탈출 조건: 돌이 아니라면 해당 방향의 4칸 탐색 종료 & 다음 방향으로 탐색

3. 출력

• 각각의 test_case번호 & 오목 판정 여부

💻 코드 작성

import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		
		
		// [input]
		int T = sc.nextInt(); 
		
		for(int t = 1; t <=T; t++) {
			
			int N = sc.nextInt();
			sc.nextLine(); 
			
			// N * N 오목
			char[][] Narr = new char[N][N];
			
			// N줄, N길이의 문자열 -> 배열에 담기
			for(int n=0; n<N; n++) {
				String string = sc.nextLine();
				for(int m=0; m<N;m++) {
					Narr[n][m]=string.charAt(m);
				}
			}//for n
			
			
			// [logic]
			// 4가지 방향 : (오른쪽) - | \ /
			int[] dx = {0, 1, 1, 1};
            int[] dy = {1, 0, 1, -1};
			
            // 플래그 변수
			boolean isFound = false;
			
			// 오목판 탐색 반복 조건: 연속된 5개 이상의 돌이 발견 X
			for(int x=0; x<N && !isFound; x++) {
				for(int y=0; y<N  && !isFound ; y++) {
					// 현재 돌이 있다면
					if(Narr[x][y]=='o') {
						// 4방향 탐색 
						for(int d=0; d<4; d++) {
							// 각 방향으로 4개의 돌이 있는가
							int cnt = 1;
							for(int i=1; i<=4; i++) {
								int nx = x + dx[d]*i;
								int ny = y +dy[d]*i;
                                // 이동한 좌표값이 유효한가
								if(nx>=0 && nx<N && ny>=0 && ny < N) {
									if(Narr[nx][ny]=='o') {
										++cnt;
									}
									else break;
								}
							}// for: 4i
                            // 조건 고민 (최소 4칸까지만 이동하므로)
							if(cnt==5) {
								isFound = true;
								break;
							}
						}// for: 4d
					}//if: o
				
				}//for: y
			}// for: x
			
			// [output]
			System.out.println("#" + t + " " + (isFound ? "YES" : "NO"));

			
		}// for: T
		
	}
}

3.복잡도 & 개선 방향

• 시간복잡도: O(N×N×4×4)=O(16N^2)=O(N^2)

[개선 방향]
1. 불필요한 범위 검사 최소화 (시작점 조건 추가)
2. 연속 5개 확인 루프 단순화
3. 반복문 깊이 줄이기 위해 방향별 체크 함수로 분리

4. 🤯 ??? & !!!

1) 방향 벡터의 정의
? 처음에는 8방향(상, 하, 좌, 우, 대각선 4개) 모두 검사해야 하나 고민함
! 오목판은 대칭 구조이므로, 오른쪽, 아래, 두 대각선 ↘, ↗만 검사해도 다른 시작점에서 나머지 방향이 커버됨 => 4방향

2) 중첩 루프 탈출 & 플래그 변수의 활용
? 오목판 전체를 탐색해야 해서 중첩된 for문이 많음
연속 5개 돌을 발견한 순간 전체 탐색을 중단해야 하는데, break만으로는 아우터 루프까지 빠져나오기 어려움
! 플래그 변수를 사용해서 외부 루프까지 결과 전달
함수 분리 후 return -> 바로 탈출 가능, 가독성 향상