[백준] 16929번 Two Dots 풀어보기 [Java]

그래프의 사이클 여부를 찾는 문제였다.

bfs문제였다. 약간 구현에 있어서 복잡한 부분이 있었던 거 같아서, 한번에 못 맞출줄 알았는데, 한번에 "맞았습니다" 나와서 기분이 좋았습니닿ㅎㅎㅎ

 

 

👨‍🏫 풀이

bfs로 풀었고, 이전에 방문 했던 적이 있는 곳을 다시 방문한다면 cycle이 생기기 때문에, 이전에 방문했던 이력이 있다면 cycle이 true로 출력하였다. 

상하좌우로 다 움직이기 때문에, 바로 이전의 방문했던 곳을 방문할 경우에 cycle이 생긴다고 말할 수 있는데, 이때는 cycle이 생기는 것이 아니기 때문에 처리해줘야 됐다. 그래서 이전에 어디서 넘어왔는지에 대한 정보도 queue에 함께 넘겨줘서 이전에 넘어왔던 곳은 체크 안하도록 하였다.

 

👨🏻‍💻 코드

package 번16929;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static boolean[] doHaveAlpha;
    static boolean[][] isVisited;
    static int[][] map;
    static int[] mX = {0,-1,0,1};
    static int[] mY = {1,0,-1,0};
    static class Node{
        int dir;
        int n;
        int m;

        public Node(int dir, int n, int m) {
            this.dir = dir;
            this.n = n;
            this.m = m;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        doHaveAlpha = new boolean[27];
        map = new int[N][M];
        Arrays.fill(doHaveAlpha, false);
        for(int i = 0 ; i < N ; i++){
            String tmp = br.readLine();
            for(int j = 0 ; j < M ; j++){
                doHaveAlpha[tmp.charAt(j) - 'A'] = true;
                map[i][j] = tmp.charAt(j) - 'A';
            }
        }
        boolean isCycle = false;
        isVisited = new boolean[N][M];
        for(int i = 0 ; i < 26 ; i++){
            if(!doHaveAlpha[i]) continue;
            for (int z = 0 ; z < N ; z++){
                Arrays.fill(isVisited[z], false);
            }
            for(int j = 0 ; j < N ; j++){
                for(int k = 0 ; k < M ; k++){
                    if(map[j][k] == i && !isVisited[j][k]){
                        isCycle = bfs(i,j,k);
                        if(isCycle){
                            System.out.println("Yes");
                            return;
                        }
                    }
                }
            }
        }
        System.out.println("No");
    }

    private static boolean bfs(int alpha, int n, int m) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(-100,n,m));
        isVisited[n][m] = true;
        while(!q.isEmpty()){
            Node cur = q.poll();
            int prevDir = (cur.dir + 2) % 4;
            for(int i = 0 ; i < 4 ; i++){
                if(i == prevDir) continue;
                int nN = cur.n + mX[i] ; int nM = cur.m + mY[i];
                if(nN < 0 || nN >= N || nM < 0 || nM >= M) continue;
                if(alpha != map[nN][nM]) continue;
                if(isVisited[nN][nM]) return true;
                isVisited[nN][nM] = true;
                q.add(new Node(i,nN,nM));
            }
        }
        return false;
    }
}