SWEA 오목판정 bfs

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AXaSUPYqPYMDFASQ&categoryId=AXaSUPYqPYMDFASQ&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=4

SW Expert Academy

	import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

class Main {
    static int T=10;
    static int N;
    static char[][] map;
    static boolean[][] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for (int l = 0; l < T; l++) {
            N = Integer.parseInt(br.readLine());
            map = new char[N][N];
            for(int i=0; i<N; i++){
                String s = br.readLine();
                for(int j=0; j<N; j++){
                    map[i][j] = s.charAt(j);
                }
            }
            //탐색
            boolean flag =false;
            search : for(int i=0; i<N; i++){
                for (int j=0; j<N; j++){
                    if(map[i][j]=='o'){
                        if(bfs(new int[]{1,-1} , new int[] {0,0} , new Node(i,j)) || bfs(new int[]{0,0} , new int[] {1,-1} , new Node(i,j)) || bfs(new int[]{1,-1} , new int[] {1,-1} , new Node(i,j)) || bfs(new int[]{1,-1} , new int[] {-1,1} , new Node(i,j)) ){
                            flag = true;
                            break search;
                        }
                    }
                }
            }
            if(flag){
                System.out.printf("#%d %s\n",l+1,"YES");
            }
            else{
                System.out.printf("#%d %s\n",l+1,"NO");
            }
        }

    }
    public static boolean bfs(int[] dx, int[] dy, Node dot){
        Queue<Node> q = new LinkedList<>();
        visited = new boolean[N][N];
        visited[dot.row][dot.col]=true;
        int count=1;
        q.add(dot);
        while(!q.isEmpty()){
            Node poll = q.poll();
            for(int i=0; i<dx.length; i++){
                int nc = dx[i]+poll.col;
                int nr = dy[i]+poll.row;
                if(nc>=0 && nc<N && nr>=0 && nr<N && !visited[nr][nc] ){
                    if(!visited[nr][nc] && map[nr][nc]=='o'){
                        visited[nr][nc]=true;
                        count++;
                        q.offer(new Node(nr,nc));
                    }
                }
            }

        }
        if(count>=5){
            return true;
        }
        else{
            return false;
        }
    }

    public static class Node{
        int col;
        int row;
        public Node(int row, int col){
            this.row=row;
            this.col=col;
        }
    }


}

dx , dy 방향에 대해서 기존 dfs와 bfs처럼 여러 방향을 혼용해서 물 퍼지듯이 가는게 아닌 한 방향을 정했으면 해방 방향으로 쭉 보고 다음 방향으로 쭉 보고 이런식으로 방향을 정해서 dfs, bfs를 수행해야 한다.

그래서 그냥 bfs 함수 만들어서 직접 매개변수로 줬다. 즉 dx dy를 한번에 정의하지 않고 그때그때 새로 만들어서 파라미터로 넘겨줬다.

 

이렇게 할 필요는 없었다.

1) 이 문제에서는 어차피 (0,0) 행부터 오른쪽 아래로 전부 탐색하면서 오목판정이 되는지를 확인할거기 때문에 모든 방향이 아닌

같은 방향은 한번만

따져주면 된다. 즉 오른쪽 위로 올라가는 방향과 왼쪽 아래로 내려가는 방향은 서로 같은 방향이기에 두번 검사할 필요 없다는 것이다. 따라서 오른쪽 , 아래 , 오른쪽 아래 대각선 , 왼쪽 아래 대각선 한번씩만 해주면 된다. 

 

2) 이에 따라서 굳이 bfs와 dfs로 할 필요는 없이 그냥 for문 돌면서 방향 하나 정해주고 그걸로 쭉 밀면서 cnt 가 5가 되는지 확인하면 된다. 

public class SWEA11315 {

	static int[][] d = { { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } }; // 오른쪽, 아래왼쪽, 아래, 아래오른쪽
	static char[][] map;
	static int N;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = Integer.parseInt(sc.nextLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(sc.nextLine());
			String answer = "NO";
			map = new char[N][N];
			for (int i = 0; i < N; i++) {
				map[i] = (sc.nextLine()).toCharArray();
			}

			gaming: for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 'o') { // 돌 발견
						for (int dd = 0; dd < 4; dd++) {
							int cnt = counting(i, j, dd);
							if (cnt == 5) { // 돌이 5개라면 게임 끝내기
								answer = "YES";
								break gaming;
							}
						}
					}
				}
			}
			System.out.println("#" + tc + " " + answer);
		}
	}

	private static int counting(int i, int j, int dd) {
		int cnt = 1; // 횟수는 1로 초기화. 이미 돌을 발견했기 때문
		int dx = i, dy = j;
		for (int g = 0; g < 4; g++) { // 총 4번 반복
			dx = dx + d[dd][0];
			dy = dy + d[dd][1];
			if (dx >= 0 && dx < N && dy >= 0 && dy < N && map[dx][dy] == 'o') {
				// 돌이 오목판 안에 있고, 돌이 존재한다면
				cnt++;
			} else {
				break;
			}
		}
		return cnt;
	}
 }