[백준] 16724 피리 부는 사나이 - DFS(깊이우선탐색) + 싸이클확인(Cycle Check) JAVA

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

16724번: 피리 부는 사나이

코드설명

DFS(깊이우선탐색) + 싸이클확인(Cycle Check) 을 활용하는 문제입니다.

 

문제에서 보면, cycleVisited와 visited 두가지 방문배열로 처리합니다.

cycleVisited로는 말그대로 싸이클 판별여부를 위한 배열입니다.

visited는 이미 싸이클로써 연산이 끝난 위치는 다시 방문할경우 값이 갱신되므로 해당 처리를 피하기 위해 사용합니다.

 

 

Simulaet함수입니다.

• simulate 메서드는 DFS(깊이 우선 탐색)를 통해 사이클을 찾는 역할을 합니다.
• 시작 위치 (r, c)에서 현재 위치를 싸이클 방문했음을 표시하고, 해당 위치에서 이동해야 할 다음 위치를 계산합니다.
• 만약 다음 위치가 범위를 벗어나면(맵을 벗어나면) 0을 반환하고 종료합니다.
• 다음 위치가 이미 방문한 곳이면(싸이클이 발견되었으면) 현재 위치를 다시 방문했음을 표시하고 0을 반환합니다.
• 위의 조건을 모두 통과하면 재귀적으로 simulate 메서드를 호출하여 다음 위치에서의 사이클 여부를 확인하고 그 값을 현재 결과에 더합니다.
• 마지막으로 현재 위치를 방문했음을 표시하고 최종적으로 결과값을 반환합니다.

 

처음에는 cycleVisited로만 처리하여서 중복싸이클이 발견되었었습니다.

아래의 반례를 통해 오류를 해결할 수 있었습니다. 

출처 : https://www.acmicpc.net/board/view/98557

4 4
RDLL
ULLL
RDRD
ULUL

정답: 3
내 오답: 7

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M;
	public static long answer = 0;
	public static int[][] arr;
	public static int[][] map;
	public static int[] target;
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static char[] animalKind;
	public static int[] amount;
	public static boolean[][] cycleVisited;
	public static int[] dx = {-1, 0, 1, 0}; // 상, 좌, 하, 우
	public static int[] dy = {0, -1, 0, 1};
	public static boolean[][] visited;
	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());
    	
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Integer>());
    	}
    	
    	map = new int[N][M];
    	cycleVisited = new boolean[N][M];
    	visited = new boolean[N][M];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		String input = st.nextToken();
    		for(int j=0;j<M;j++) {
    			map[i][j] = input.charAt(j) - 'A';
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(cycleVisited[i][j] == false) {
    				answer += simulate(i, j);
    			}
    		}
    	}
    	
    	System.out.println(answer);
	}
	
	//즉, 어디서든 DFS를 호출하면 도착할 수 있어야한다라는 의미로 보인다. 즉, 싸이클의 개수를 찾는 문제인듯합니다.
	public static int simulate(int r, int c) {
		if(cycleVisited[r][c] == true) return 1; //만약 이미 방문햇더라면 싸이클이 발견되므로 1을 반환해줍니다.
		cycleVisited[r][c] = true; //싸이클 판별을 위해 시작점에서 방문처리를 합니다.
		int result = 0;
		int nr = 0, nc = 0;
		if(map[r][c] == 'U' - 'A') {
			nr = r + dx[0];
			nc = c + dy[0];
		}
		if(map[r][c] == 'L' - 'A') {
			nr = r + dx[1];
			nc = c + dy[1];
		}
		if(map[r][c] == 'D' - 'A') {
			nr = r + dx[2];
			nc = c + dy[2];
		}
		if(map[r][c] == 'R' - 'A') {
			nr = r + dx[3];
			nc = c + dy[3];
		}
		
		
		if(nr < 0 || nr >= N || nc < 0 || nc >= M) return 0;
		if(visited[nr][nc] == true) {
			visited[r][c] = true;
			return 0;
		}
		
		result += simulate(nr, nc);
		visited[r][c] = true;
		
		
		return result;
	}
	
}