문제 링크

성능 요약

메모리: 28104 KB, 시간: 316 ms

분류

자료 구조, 깊이 우선 탐색, 분리 집합, 그래프 이론, 그래프 탐색

제출 일자

2025년 1월 19일 17:16:22

문제 설명

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다.

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.

지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

풀이

느낀점

• 지난 번 풀었던 텀프로젝트와 비슷했다.
• 텀프로젝트를 풀때는 팀을 이루지 않은 학생의 수를 구해야 해서 처리 조건을 설정하기가 까다로웠는데, 이번에는 사이클의 개수만 세면 되는 구조라서 더욱 간단했다. 텀프로젝트를 한번 더 풀어보는게 나을수도,,
• 생각보다 너무 쉽게 풀려서 혹시 몰라 테케도 직접 하나 만들어봤다,, 적절한 테케였는지는 모르겠으나,,

설계 : 10분

• 답이 이루어지는 규칙을 보니, 사이클의 개수를 구하는 문제같았다.
• 지도 밖으로 이동하는 입력은 주어지지 않는다고 했으니, 사이클 내부에 포함되지 않는 칸도 어차피 특정한 사이클로 향하게 되어 있다.
• 즉, bfs를 시작하면 방문한 곳들은 전부 사이클이거나, 사이클로 향하는 것이다. (방향은 각 하나씩이기 때문에, 같은 지점을 가진 두개의 사이클은 존재할 수 없다.)
• 따라서 탐색 중 이미 방문한 곳을 만나면 현재 탐색중에 사이클이 이루어졌거나, 이전 탐색에서 방문한 사이클로 향하는 경로일 것이다. (이걸 분리해서 방문체크를 해주는 것이 중요하다)
• 모든 노드를 순회하며 방문하지 않는 노드부터 bfs를 시작한다. 방문체크는 visited[][]와 cycle[][] 로 2가지를 준비했다.
• 현재 탐색중인 경로는 visited로 판단하고, 이미 어떤 사이클이거나 사이클로 향하는 노드로 판단된 것들은 cycle로 기록한다.
• bfs로 재귀를 통해 방향대로 이동하는데, cycle이면 사이클 개수를 늘리지 않고 return, visited면 사이클 개수를 늘리고 return, 둘다 아니라면 계속해서 이동한다.
• 재귀함수를 호출하기 전 visited처리하고, 재귀함수에서 빠져나오면 어딘가에서 판단이 마쳐진 상태임으로 cycle을 처리한다.
• 최종적으로 기록된 사이클의 개수가 answer이다.
• 직접 작성한 Test Case

  • input

    4 4
    DLDL
    RDLD
    DURU
    RRUU

  • output

    2

코드(Java)

• 구현 시간: 15분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 피리 부는 사나이_16724
 * Date: 2025.01.19
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int[][] map;
	static boolean[][] visited;
	static boolean[][] cycle;
	static int[] dr = new int[] {-1, 0, 1, 0};
	static int[] dc = new int[] {0, 1, 0, -1};
	static int answer;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);

		map = new int[n][m];
		for (int i = 0; i < n; i++) {
			char[] chars = br.readLine().toCharArray();
			for (int j = 0; j < m; j++) {
				if (chars[j] == 'R') map[i][j] = 1;
				else if (chars[j] == 'D') map[i][j] = 2;
				else if (chars[j] == 'L') map[i][j] = 3;
			}
		}

		visited = new boolean[n][m];
		cycle = new boolean[n][m];
		answer = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!visited[i][j]) bfs(i, j);
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}

	private static void bfs(int r, int c) {
		if (cycle[r][c]) return;
		if (visited[r][c]) {
			answer++;
			return;
		}
		visited[r][c] = true;
		int direc = map[r][c];
		bfs(r+dr[direc], c+dc[direc]);
		cycle[r][c] = true;
	}
}