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

문제 설명

• https://www.acmicpc.net/problem/16724
• 어디에서 이동해도 SAFE ZONE에 도달할 수 있도록 최소 SAFE ZONE을 만들어야 합니다.

접근법

• 2차원 배열에서 모든 위치를 방문하면서 최소값을 구해야 하기 때문에 BFS를 활용했습니다.
• 처음에는 단순히 BFS의 실행 횟수를 정답으로 출력했습니다. 이 경우 아래의 반례가 존재합니다.
  ----
  DLLL
  DLRU
  RRRU
  ----
  BFS를 실행한다고 반드시 SAFE ZONE을 설치할 필요는 없습니다. 다음 위치가 SAFE ZONE으로 갈 수 있는 발판이라면 SAFE ZONE을 설치하지 않습니다.
• BFS가 마무리됐을 때 끊기는 지점이 현재 BFS로 방문한 곳인 경우에만 SAFE ZONE을 추가합니다.
  
  • 검은색은 자기자신으로 끝났기 때문에 SAFE ZONE을 추가해야 합니다.
  • 빨간색은 자기자신으로 끝나지 않았기 때문에 SAFE ZONE을 추가하지 않아도 됩니다.

• 방문배열을 boolean이 아닌 int로 표현하면 현재 방문한 곳인지를 체크할 수 있습니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		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());
		char[][] board = new char[N][M];
		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
		}
		int[][] v = new int[N][M];
		int cnt = 0;
		int answer = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(v[i][j] == 0) {
					v[i][j] = ++cnt;
					answer += BFS(board,v,i,j,N,M,cnt);
				}
			}
		}	
		System.out.println(answer);
	}
	
	public static int BFS(char[][] board, int[][] v, int x, int y,int N, int M, int cnt) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {x,y});
		while(!q.isEmpty()) {
			int[] now = q.poll();
			int[] next = move(now[0],now[1],board[now[0]][now[1]]);
			int nx = next[0];
			int ny = next[1];
			if(0 <= nx && nx < N && 0 <= ny && ny < M) {
				if(v[nx][ny] == 0) {
					q.add(new int[] {nx,ny});
					v[nx][ny] = cnt;					
				}else {
					if(v[nx][ny] == cnt) {
						return 1;
					}else {
						return 0;
					}
				}
			}
		}
		return -999;
	}

	public static int[] move(int x, int y, char d) {
		if(d == 'D') {
			return new int[]{x+1,y};
		}else if(d == 'U') {
			return new int[] {x-1,y};
		}else if(d == 'L') {
			return new int[] {x,y-1};
		}else {
			return new int[] {x,y+1};
		}
	}
}