[백준/JAVA] 17070번: 파이프 옮기기 1

🔺 문제

17070번: 파이프 옮기기 1

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static int N;
    public static int map[][];
    public static int answer;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        map = new int[N + 1][N + 1];
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 1 ; j <= N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        answer = 0;
        DFS(1, 2, 0);
        
        System.out.println(answer);
        br.close();
    }
    
    // DFS
    public static void DFS(int x, int y, int direction) {
        // 종료 조건
        if(x == N && y == N) {
            answer++;
            return;
        }
        
        // 가로 방향인 경우, → ↘  이동 가능
        if(direction == 0) {
            if(y + 1 <= N && map[x][y + 1] == 0)    // → 이동
                DFS(x, y + 1, 0);
        }
        // 세로 방향인 경우, ↓ ↘ 이동 가능
        else if(direction == 1) {
            if(x + 1 <= N && map[x + 1][y] == 0)    // ↓ 이동 
                DFS(x + 1, y , 1);
        }
        // 대각선 방향인 경우, → ↓ ↘ 이동 가능
        else if(direction == 2) {
            if(y + 1 <= N && map[x][y + 1] == 0)    // → 이동 
                DFS(x, y + 1, 0);
            if(x + 1 <= N && map[x + 1][y] == 0)    // ↓ 이동 
                DFS(x + 1, y , 1);
        }
        
        // [공통] 파이프가 어떤 방향이든, ↘ 이동
        if(y + 1 <= N && x + 1 <= N && map[x][y + 1] == 0 && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0) {
            DFS(x + 1, y + 1, 2);
        }
    }
}

✅ 해결 아이디어
✔ DFS : (N,N) 으로 이동시키는 모든 방법의 개수 구하기
○ 가로 → 가로 / 대각선
○ 세로 → 세로 / 대각선
○ 대각선 → 가로/세로 / 대각선

 

 

---

🔺 다른 풀이들

- 과정 설명 풀이 굿!

[백준 17070] - 파이프 옮기기(JAVA)

 

 

- DP 풀이.. 라는데 DFS로 푸는 게  오히려 간단한 것 같다...

[BOJ] 17070 - 파이프 옮기기 1 JAVA

---

💬 느낀 점

돌아가라 머리머리...!

 

 

1회독	2회독	3회독	4회독	5회독
V	240524

---

(참고)

✔ 풀이 참고

[BOJ] 백준 17070번 : 파이프 옮기기 1 (JAVA)

 

✔ BFS가 안 되는 이유

[BOJ] 백준 17070번 : 파이프 옮기기 1 자바 (JAVA)