백준 16724번 : 피리 부는 사나이

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

16724번: 피리 부는 사나이

 

 

 

 

 

 

문제

• 성우가 정해놓은 방향대로 움직이기 시작한다.
  • 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동
• 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력

 

제한사항

• N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)
• 지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

 

출처 : https://www.acmicpc.net/problem/16724

 

 

예제 입출력

입력

3 4
DLLL
DRLU
RRRU

출력 : 2

 

 

 

 

 

풀이

• DFS(깊이 우선 탐색)

설정한 방향에 따라 계속 이동하므로 그래프 탐색을 DFS로 했다. 한 점을 기준으로 DFS 탐색을 하여 한 사이클을 구한다.

 

 

• 사이클 파악하기

 SAFE ZONE은 사이클이 시작되는 루트 노트에 있어야 한다. 그래서 방문하지 않은 지점에 대해 계속 방향대로 탐색을 하여 탐색이 끝나면 SAFE ZONE을 설치하도록 했다.

 

입출력 예시

 

 

 하지만 아래 그림과 같이 다른 지점에서 DFS 탐색을 했을 때, 같은 사이클인 지점에서 탐색을 끝내는 경우도 있다. 같은 사이클이므로 SAFE ZONE을 설치하면 안된다. 사이클을 새로 만드는 건지 아닌지 구분해줄 필요가 있다.

 

 

 

• 그래프 방문 체크 : int 2차원 배열

사이클을 새로 만드는 건지 아닌지 구분하기 위해 DFS 시작할 때마다 새 번호를 붙여 방문 체크를 해준다. DFS가 종료될 지점의 번호가 시작할 때의 번호와 같다면 새로 사이클을 완성하게 되는 것이고, 현재의 번호와 다르다면 이전에 이미 만든 사이클인 것이다.

 

새로 사이클 형성하는 경우

 

기존 사이클인 경우

 

 

 

 

 

코드

import java.util.*;
import java.io.*;

public class BOJ_피리부는사나이 {
	static int N, M;
	static char[][] graph;
	static int[][] visited;
	static int[] dx = {-1, 1, 0, 0}; //U, D, L, R
	static int[] dy = {0, 0, -1, 1};
	static int count;

	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()); //열의 수
		
		graph = new char[N][M];
		
		for(int i = 0; i < N; i++) {
			char[] chArr = br.readLine().toCharArray();
			
			for(int j = 0; j < M; j++) {
				graph[i][j] = chArr[j];
			}
		}
		
		//탐색
		visited = new int[N][M]; //방문 표시 : 0(방문X), 1이상(방문O)
		count = 0; //정답 : SAFE ZONE의 최소 개수
		int idx = 0; //탐색 인덱스
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(visited[i][j] == 0) { //방문한 적 없으면
					dfs(i, j, ++idx); //탐색
				}
			}
		}
		
		//출력
		System.out.println(count);
	}

	public static void dfs(int x, int y, int idx) {
		visited[x][y] = idx;
		
		int nx = x; //다음 이동 행
		int ny = y; //다음 이동 열
		
		switch(graph[x][y]) {
			case 'U' :
				nx += dx[0];
				ny += dy[0];
				break;
			case 'D' :
				nx += dx[1];
				ny += dy[1];
				break;
			case 'L' :
				nx += dx[2];
				ny += dy[2];
				break;
			case 'R' :
				nx += dx[3];
				ny += dy[3];
				break;
		}
		
		if(0 <= nx && nx < N && 0 <= ny && ny < M) {
			if(visited[nx][ny] == 0) { //방문한 적 없음
				dfs(nx, ny, idx);
			} else { //방문한 적 있음
				if(visited[nx][ny] == idx) { //사이클 새로 완성
					count++;
					return;
				}
				//현재의 인덱스와 다름(=이전에 만든 사이클)
			}
		}
	}

}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• visited 배열을 int형으로 해서 구역(사이클)을 구별하기