[알고리즘] Java / 백준 / 피리 부는 사나이 / 16724

[알고리즘] Java / 백준 / 피리 부는 사나이 / 16724

문제

문제 링크

접근 방식

이 문제의 핵심은 사이클 갯수를 세는 것이다.

사이클 갯수를 세기 위해서는 union-find 방법이 있고 dfs로도 가능하다.

dfs로 풀이할 경우

1. 방문하지 않았던 점에서 dfs를 시작, 방문 했던 점을 탐색할 때 까지 dfs 반복
2. 방문 했던 점을 탐색했다면 해당 점이 사이클 검사를 했는지를 체크하고 하지 않았다면 사이클 갯수를 늘린 후 처음부터 방문했던 모든 점들의 사이클 검사를 true로 한다.

코드

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

public class Main_16724 {

	static boolean[][] visited;
	static boolean[][] finished;
	static int safezone;
	static int[][] map;
	public static void main(String[] args) throws IOException{
		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());
		
		map = new int[N][M];
		
		for(int i=0;i<N;i++) {
			String line = br.readLine();
			for(int j=0;j<M;j++) {
				int c = line.charAt(j);
				if(c == 'U') map[i][j] = 0;
				else if(c == 'D') map[i][j] = 1;
				else if(c == 'L') map[i][j] = 2;
				else if(c == 'R') map[i][j] = 3;
			}
		}
		
		
		// 사이클의 개수를 세면 된다.
		visited = new boolean[N][M]; // 방문한 위치
		finished = new boolean[N][M]; // 사이클인지 확인한 위치
		safezone = 0;
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(!visited[i][j]) dfs(i,j);
			}
		}
		
		System.out.println(safezone);
		
	}
	
	static int dr[] = {-1,1,0,0};
	static int dc[] = {0,0,-1,1};
	public static void dfs(int r, int c) {
		
		visited[r][c] = true;
		
		int nr = r + dr[map[r][c]];
		int nc = c + dc[map[r][c]];
		
		if(!visited[nr][nc]) {
			dfs(nr,nc);
		}else {
			
			if(!finished[nr][nc]) safezone++;
		}
		
		finished[r][c] = true;
	}

}