[SWEA] 11315. 오목 판정

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

접근 방법

백트래킹을 이용했다.

왼쪽 위에서부터 차례대로 탐색하기 때문에 4 방향(아래, 오른쪽, 오른쪽 아래, 왼쪽 아래)만 비교했다.

돌이 있을 경우에만 탐색했고, 도중 리턴 하는 경우는

(1) 연속된 돌이 5개일 경우

(2) 검사하려는 인덱스가 초과일 경우

(3) 해당 위치에 돌이 없을 경우 이다.

1번의 경우 check(ck)를 유효화해서 해당 방향의 탐색이 끝나면 더 이상의 탐색을 하지 않을 수 있다.

 

소스 코드

import java.util.*;
import java.io.*;
 
public class Solution {
    static char[][] map;
    static int N;
    static int[] dx = {1, 0, 1, 1};
    static int[] dy = {0, 1, 1, -1};
    static boolean ck;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
        int T = Integer.valueOf(br.readLine());
        for(int t=1; t<=T; t++) {
            ck = false;
            N = Integer.valueOf(br.readLine());
            map = new char[N][N];
            for(int i=0; i<N; i++)
                map[i] = (br.readLine()).toCharArray();
             
            for(int i=0; i<N*N; i++) {
                int x = i/N;
                int y = i%N;
                if(map[x][y] == 'o') {
                    back(x+dx[0], y+dy[0], 0, 1); if(ck) break;
                    back(x+dx[1], y+dy[1], 1, 1); if(ck) break;
                    back(x+dx[2], y+dy[2], 2, 1); if(ck) break;
                    back(x+dx[3], y+dy[3], 3, 1); if(ck) break;
                }
            }
            String result = ck ? "YES" : "NO";
            System.out.println("#" + t + " " + result);
        }
    }
    static void back(int x, int y, int n, int c) {
        if(x < 0 || x >= N || y < 0 || y >= N) {
            if(c >= 5) ck = true;
            return;
        }
        if(map[x][y] != 'o') {
            if(c >= 5) ck = true;
            return;
        }
        back(x+dx[n], y+dy[n], n, c+1);
    }
}