[백준 16724] 피리 부는 사나이 / 자바 / dfs

#문제         

레벨: G3
알고리즘: dfs
풀이시간: 40분
힌트 참조 유무:

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

---

#문제 풀이        

문제를 쉽게 설명하자면 "시간은 상관없이 방향에 따라 이동할 때 언젠가는 세이프존에 들어갈 수 있게 해라"이다. 문제에 나와있지는 않지만 방향에 따라 갔을 때 배열을 벗어나는 경우는 없다. 이 부분이 설명이 안 되어있는게 아쉽긴 하다. 

그럼 우린 dfs를 통해 싸이클을 돌면 된다. 배열 내에 싸이클의 개수가 답인 거다.

dfs+cycle 개념이 이해가 안 간다면 아래에 관련 문제 링크 참조해둘테니 연습해보면 좋을 것이다.

---

#풀이 코드      

import java.util.Scanner;

public class Main {
   static int N, M;
   static char[][] map;
   static int[][] visited;
   static int SAFE_ZONE_COUNT = 0;

   static int[] dx = {-1, 1, 0, 0}; // U, D, L, R 
   static int[] dy = {0, 0, -1, 1};

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       N = sc.nextInt();
       M = sc.nextInt();
       sc.nextLine(); // 개행 문자 처리

       map = new char[N][M];
       visited = new int[N][M];

       // 입력
       for (int i = 0; i < N; i++) {
           String line = sc.nextLine();
           for (int j = 0; j < M; j++) {
               map[i][j] = line.charAt(j);
               visited[i][j] = 0; 
           }
       }

       // 모든 위치에서 사이클 찾기
       for (int i = 0; i < N; i++) {
           for (int j = 0; j < M; j++) {
               if (visited[i][j] == 0) {
                   dfs(i, j);
               }
           }
       }

       System.out.println(SAFE_ZONE_COUNT);
   }

   static void dfs(int x, int y) {
       visited[x][y] = 1;  // 현재 경로에 포함
       
       // 다음 위치 계산
       int nx = x + dx[getDirection(map[x][y])];
       int ny = y + dy[getDirection(map[x][y])];
       
       // 다음 위치가 방문하지 않았으면 계속 탐색
       if (visited[nx][ny] == 0) {
           dfs(nx, ny);
       } 
       // 현재 탐색 중인 경로에서 방문한 곳(1)을 만나면 사이클 발견
       else if (visited[nx][ny] == 1) {
           SAFE_ZONE_COUNT++;
       }
       
       visited[x][y] = 2;  // 탐색 완료
   }

   // 방향 문자를 인덱스로 변환
   static int getDirection(char c) {
       switch (c) {
           case 'U': return 0;
           case 'D': return 1;
           case 'L': return 2;
           case 'R': return 3;
       }
       return -1;
   }
}

 

---

#비슷한 유형      

 

https://jsw5913.tistory.com/179

 

 

https://jsw5913.tistory.com/171

[백준 9466] 텀 프로젝트 / 자바 / dfs + cycle