BOJ -16929 ) Two Dots

---

https://www.acmicpc.net/problem/16929

16929번: Two Dots

 

---

노드간 사이클을 찾는 문제였다. DFS풀이는 바로생각났지만, BFS로 궁금한점이 생겨서 테스트해봤던 문제,

 

사이클이 존재하면 최단거리로 도달하는 시간만 체크해주면 풀릴거같았다.

 

예를들어

 

AAAAA

BBBBA

AAABA

ABABA

AAAAA

 

와 같은 입력에서 어느 A에서 시작하더라도, 같은 시간으로 도달하는 한점이 생긴다 => 사이클이있다.

 

이 가설?같은거를 증명해보았는데 문제제약조건인 그래프크기는 4이상인것도 만족시키는 문제..

---

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

public class TwoDot {
	public static class node {
		char c;
		int y,x,time;
		public node(char c, int y, int x, int time) {
			super();
			this.c = c;
			this.y = y;
			this.x = x;
			this.time = time;
		}
		 
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		char map[][] = new char[n+1][m+1];
		int  visit[][] = new int[n+1][m+1];
		int dir[][] = {{1,0},{0,1},{-1,0},{0,-1}};
		ArrayDeque<node> dq = new ArrayDeque<>();
		for(int i = 1 ; i<=n ; i++) {
			char temp[] = br.readLine().toCharArray();
			for(int j =1 ; j <= m ; j++) {
				map[i][j] = temp[j-1];
			}
		}
		String answer = "No";
		top :
		for(int i = 1 ; i <=n ; i++) {
			for(int j = 1 ;j<= m ; j++) {
				if(visit[i][j] ==0) {
					visit[i][j]=1;
					dq.add(new node(map[i][j] , i,j,1));
					while(!dq.isEmpty()) {
						node now = dq.poll();
						for(int k= 0 ; k <4 ; k++) {
							int ny = now.y + dir[k][0];
							int nx = now.x + dir[k][1];
							if(ny>=1 && nx >=1 && ny <= n && nx <= m && now.c == map[ny][nx]) {
								if(visit[ny][nx]==0) {
									visit[ny][nx] = now.time+1;
									dq.add(new node (now.c  , ny , nx , now.time+1));
								} else if(visit[ny][nx] == now.time+1) {
									answer ="Yes";
									break top;
								}
							}
						}
						
					}
				}
			}
		}
		System.out.println(answer);
		
	}
}

---