[백준] 17070: 파이프 옮기기 1 (Java/Python)

Yoon Uk·2023년 2월 1일

DFS Java python 백준 알고리즘

알고리즘 - 백준

목록 보기

81/130

문제

BOJ 17070: 파이프 옮기기 1 https://www.acmicpc.net/problem/17070

풀이

조건

파이프는 항상 빈 칸만 차지해야 한다.
파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다.
파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.
가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구한다.

풀이 순서

DFS를 사용해 해결한다.
파이프의 모양에 따라 움직일 수 있는 방법이 다르기 때문에 조건에 맞춰 가능한 케이스만 다음 깊이로 진행할 수 있도록 한다.

코드

Python

import sys

N = int(sys.stdin.readline())

board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dx = [0, 1, 1]  # 가로, 세로, 대각선 순으로
dy = [1, 0, 1]

# 파이프가 범위 안에 있는지 확인하는 메소드
def is_range(nx, ny):
    # global board
    # global N
    if nx >= N or ny >= N or nx < 0 or ny < 0 or board[nx][ny] == 1:
        return False
    return True

answer = 0 # 출력할 정답


# dir -> 0: 가로// 1: 세로// 2: 대각선 상태
def dfs(x, y, dir):
    global answer
    # global N
    # global board
    # 목적지에 도달하면 종료
    if x == N - 1 and y == N - 1:
        answer += 1
        return

    for t in range(3):
        # 세로 상태인데 가로로 옮기려고 할 때, 가로 상태인데 세로로 옮기려고 할 때 체크
        if (t == 0 and dir == 1) or (t == 1 and dir == 0):
            continue

        nx = x + dx[t]
        ny = y + dy[t]
		
        # 범위 체크
        if not is_range(nx, ny):
            continue
        # 대각선인데 양 옆이 벽인지 체크
        if (t == 2 and board[x + 1][y] == 1) or (t == 2 and board[x][y + 1] == 1):
            continue

        dfs(nx, ny, t)

dfs(0, 1, 0) # 파이프의 끝은 처음에 (0, 1)의 위치, 가로모양(0)으로 놓여있다.

print(answer)

Java

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

public class Main {
	
	static int N;
	static int[][] board;
	static int answer;
	
	static int[] dx = {0, 1, 1}; // 가로먼저
	static int[] dy = {1, 0, 1};

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		
        // 공간 입력
		board = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		answer = 0;
        
		dfs(0, 1, 0);
        
		System.out.print(answer);

	}
	
	// dir-> 0: 가로 // 1: 세로 // 2: 대각선
	static void dfs(int x, int y, int dir) {
    	// 목적지에 도달하면 종료
		if(x == N-1 && y == N-1) {
			answer++;
			return;
		}
		
		for(int t=0; t<3; t++) {
        	// 세로 상태인데 가로로 옮기려고 할 때, 가로 상태인데 세로로 옮기려고 할 때 체크
			if((t==0 && dir==1) || (t==1 && dir==0)){
				continue;
			}
			
			int nx = x + dx[t];
			int ny = y + dy[t];
            // 범위 체크
			if(!isRange(nx, ny)) {
				continue;
			}
			// 대각선인데 양 옆이 벽인지 체크
			if((t == 2 && board[x+1][y] == 1) || (t == 2 && board[x][y+1] == 1)) {
				continue;
			}
			
			dfs(nx, ny, t);
		}
	}	
	
    // 범위 체크하는 메소드
	static boolean isRange(int x, int y) {
		if(x < 0 || y < 0 || x >= N || y >= N || board[x][y] == 1) {
			return false;
		}
		return true;
	}
}