BOJ 16929

2020-10-21

위 문제는 백준 사이트의 알고리즘 16929문제에 관한 설명입니다.

문제

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

점 k개 d1, d2, …, dk로 이루어진 사이클의 정의는 아래와 같다.

  • 모든 k개의 점은 서로 다르다.
  • k는 4보다 크거나 같다.
  • 모든 점의 색은 같다.
  • 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다.

두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

입력

첫째 줄에 게임판의 크기 N, M이 주어진다.

둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다.

게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다.

점의 색은 알파벳 대문자 한 글자이다.

출력

사이클이 존재하는 경우에는 “Yes”, 없는 경우에는 “No”를 출력한다.

소스코드


package day1021;

import java.util.Scanner;

public class Main {
	static int n, m;
	static char[][] color;
	static boolean [][] visit;
	static int[][] count;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		m = scanner.nextInt();
		
		color = new char[n][m];//map처럼 쓴다.
		count = new int[n][m];
		visit = new boolean[n][m];
		
		for(int i = 0 ; i < n; i++) {
			color[i] = scanner.next().toCharArray();
		}
		
		for(int i = 0 ; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(isCycle(i,j,color[i][j],1)) {
					System.out.println("Yes");
					return;
				}
			}
		}
		System.out.println("No");
		scanner.close();
	}
	
	static boolean isCycle(int x, int y, int c, int length) {
		if(visit[x][y]) {
			return length - count[x][y] >=4;
		}
		visit[x][y] =true;
		count[x][y] = length;
		for(int dir = 0 ; dir < 4; dir++) {
			int nextX = x + dx[dir];
			int nextY = y + dy[dir];
			if(0 <= nextX && 0 <= nextY && nextX < n && nextY < m) {
				if(color[nextX][nextY] == c) {
					if(isCycle(nextX,nextY, c, length+1)) return true;
				}
			}
		}
		return false;
	}
}

이번문제는 dfs로 풀었습니다.

하나씩 살펴봅니다.


		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		m = scanner.nextInt();
		
		color = new char[n][m];//map처럼 쓴다.
		count = new int[n][m];
		visit = new boolean[n][m];
		
		for(int i = 0 ; i < n; i++) {
			color[i] = scanner.next().toCharArray();
		}

평범한 입력부 입니다.

color는 이중 배열로

scanner로 한줄을 받을 수 있는 next()와

char형 배열로 만들어 주는 toCharArray()를 이용해

char형 배열 한줄을 한번에 받아줍니다.

		for(int i = 0 ; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(isCycle(i,j,color[i][j],1)) {
					System.out.println("Yes");
					return;
				}
			}
		}
		System.out.println("No");
		scanner.close();

각 점마다 isCycle()을 동작시킵니다.

만약 true가 반환된다면 Cycle이 있다는 뜻으로 Yes를 리턴합니다.

  • return을 안하면 yes라고 출력 후 다시 돌면서 원치 않는 결과를 얻을 수 있습니다.
	static boolean isCycle(int x, int y, int c, int length) {
		if(visit[x][y]) {
			return length - count[x][y] >=4;
		}
		visit[x][y] =true;
		count[x][y] = length;
		for(int dir = 0 ; dir < 4; dir++) {
			int nextX = x + dx[dir];
			int nextY = y + dy[dir];
			if(0 <= nextX && 0 <= nextY && nextX < n && nextY < m) {
				if(color[nextX][nextY] == c) {
					if(isCycle(nextX,nextY, c, length+1)) return true;
				}
			}
		}
		return false;
	}

return을 하는 조건을 봅시다.

만약 방문을 했던 곳이라면 그 곳과 사이클이 연결되는지를 확인해야합니다.

이때 길이가 4이상인 이유는 가장작은 사이클인 4개의 점을 나타냅니다.

그렇게 지나온점에 있는 길이와 여태까지 지나온 길이를 비교해서 4이상인지 확인합니다.

맞다면 사이클이 존재한다는 것.

아니라면 아래쪽을 이어서 동작합시다.

방문처리를 하고, count에 지나온 길이를 기록합시다.

이후 4방향을 다 둘러보면서 같은 색상이 있는지 확인합니다.

		for(int dir = 0 ; dir < 4; dir++) {
			int nextX = x + dx[dir];
			int nextY = y + dy[dir];
			if(0 <= nextX && 0 <= nextY && nextX < n && nextY < m) {
				if(color[nextX][nextY] == c) {
					if(isCycle(nextX,nextY, c, length+1)) return true;
				}
			}
		}

같은 색상이 있다고 나타나면 다음 위치와 dfs를 연결하면서 사이클이 있는지 확인합시다.

전부 확인했는데 사이클이 안나온다면 false를 리턴합니다.

Two Dots