코테/백준

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

imname1am 2023. 5. 24. 20:16
반응형

🔺 문제

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

 

 

🔺 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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(120);
        
        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 + 10);
        }
        // 세로 방향인 경우, ↓ ↘ 이동 가능
        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 + 10);
            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 + 12);
        }
    }
}
cs
✅ 해결 아이디어
✔ DFS : (N,N) 으로 이동시키는 모든 방법의 개수 구하기
○ 가로 → 가로 / 대각선
○ 세로 → 세로 / 대각선
○ 대각선 → 가로/세로 / 대각선

 

 


🔺 다른 풀이들

- 과정 설명 풀이 굿!

 

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

[문제] 출처 - https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다.

dding9code.tistory.com

 

 

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

 

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

www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로

codeung.tistory.com


💬 느낀 점

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

 

 

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

(참고)

✔ 풀이 참고

 

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

문제의 링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다.

steady-coding.tistory.com

 

BFS가 안 되는 이유

 

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

# 그래프 이론 # 그래프 탐색 # 다이나믹 프로그래밍 🥇 난이도 - Gold 5

velog.io

 

반응형