16929_Two Dots

사용 알고리즘: bfs

사용 언어: java

 

package afterMiracom_0618;

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

public class Main_bj_16929_TwoDots {
	
	static int n, m;
	static char[][] map;
	static int[] dx = {0,1,0,-1}; //오른쪽, 아래쪽 , 왼쪽, 위쪽
	static int[] dy = {1,0,-1,0};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		map = new char[n][m];
		for(int i=0; i<n; i++) {
			String s = sc.next();
			for(int j=0; j<m; j++) {
				map[i][j] = s.charAt(j);
			}
		}
		//입력 끝
		
		boolean isCycle = startCycle();
		
		if(isCycle) System.out.println("Yes");
		else System.out.println("No");
	}

	private static boolean startCycle() {
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				
				if (canCycle(i, j)) {
					return true;
				}
			}
		}
		return false;
	}

	private static boolean canCycle(int x, int y) {
		Queue<Path> q = new ArrayDeque<>();
		
		ArrayList<Point> al = new ArrayList<>();
		al.add(new Point(x, y));
		
		boolean[][] visit = new boolean[n][m];
		
		q.add(new Path(new Point(x, y), al, visit));
		char color = map[x][y];
		
		while(!q.isEmpty()) {
			Path p = q.poll();
			
			if(p.al.size() == 1) { //이때는 오른쪽으로만 움직여야 함
				int nx = p.point.x + dx[0];
				int ny = p.point.y + dy[0];
				
				if (withinRange(nx, ny) && !visit[nx][ny] && color==map[nx][ny]) {
					visit[nx][ny] = true;
					al.add(new Point(nx, ny));
					q.add(new Path(new Point(nx, ny), al, visit));
				}
			}
			else if(p.al.size() == 2) { //이때는 오른쪽, 아래쪽으로만 움직여야 함
				for(int d=0; d<2; d++) {
					int nx = p.point.x + dx[d];
					int ny = p.point.y + dy[d];
					
					if (withinRange(nx, ny) && !visit[nx][ny] && color==map[nx][ny]) {
						visit[nx][ny] = true;
						al.add(new Point(nx, ny));
						q.add(new Path(new Point(nx, ny), al, visit));
					}
				}
			}
			else { //4방으로 움직일 수 있음 && 사이클 확인
				if(p.al.get(0).equals(p.point)) { //사이클 완성
					return true;
				}
				
				for(int d=0; d<4; d++) {
					int nx = p.point.x + dx[d];
					int ny = p.point.y + dy[d];
					
					if (withinRange(nx, ny) && !visit[nx][ny] && color==map[nx][ny]) {
						visit[nx][ny] = true;
						al.add(new Point(nx, ny));
						q.add(new Path(new Point(nx, ny), al, visit));
					}
				}
			}
			
		}
		return false;
	}

	private static boolean withinRange(int nx, int ny) {
		if(nx>=0 && ny>=0 && nx<n && ny<m) return true;
		return false;
	}

}

class Path {
	Point point;
	ArrayList<Point> al;
	boolean[][] visit;
	
	public Path(Point point, ArrayList<Point> al, boolean[][] visit) {
		this.point = point;
		this.al = al;
		this.visit = visit;
	}
}

 

인사이트:

처음에 boolean[] visit배열로만 했다가 모든 예시에서 사이클이 가능하다고 나왔다.

이유: 시작점에서 한 번 움직인 이후, 4방 탐색을 하면 시작점으로 되돌아 갈 수 있으니까 무조건 사이클이 가능하다고 나온다

해결방법: al에 움직인 경로를 저장해두면서, al의 사이즈가 1일때 (=시작점만 방문했을 때)는 오른쪽으로만 가게 함, al의 사이즈가 2일때(=시작점에서 오른쪽으로 움직였을 때)는 오른쪽이나 아래쪽으로만 가게 함, 그 외 경우는 사이클이 되나 확인하고 + 4방 전부 탐색 가능

이게 되는 이유: x좌표가 작은 순 -> y좌표가 작은 순 으로 시작점을 가지기 때문에 오른쪽->아래쪽으로 탐색하는 게 맞다 (혹은 아래쪽 -> 오른쪽)