BOJ 17070번: 파이프 옮기기1

문제

문제 바로가기> BOJ 17070번: 파이프 옮기기1

17070번: 파이프 옮기기 1

 

풀이

DFS 탐색을 통해 간단하게 해결할 수 있는 문제다!

 

  1. 파이프의 마지막 부분(초기값 : (1,2))을 추적해가면서 DFS 탐색 진행

    (가로, 세로, 대각선 이동 방법이 다름)

 

  2. 종료 조건 : 범위를 벗어나는 경우, 빈칸이어야하는 부분인 벽인 경우

    (범위를 벗어나는 경우를 확인할 때, N보다 큰지만 확인해주면 된다. 더하는 방향으로만 이동하기 때문!)

 

  3. (N, N)에 도달한 경우 : `ans++`

 

C++

#include<iostream>
#define MAX 17
using namespace std;

int N, ans=0;
int home[MAX][MAX];

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) cin >> home[i][j];
	}
}

void dfs(int r, int c, int d) {

	if (r > N || c > N || home[r][c]) return; // 범위를 벗어나거나, 벽인 경우
	if (d == 2 && (home[r - 1][c] || home[r][c - 1])) return; // 대각선 이동시 필요한 공간이 벽인 경우
	if (r == N && c == N) { // 한쪽 끝으로 이동 성공
		ans++;
		return;
	}
	if (d == 0) { // 가로
		dfs(r, c + 1, 0); // 가로
		dfs(r + 1, c + 1, 2); // 대각선
	}
	else if (d == 1) { // 세로
		dfs(r + 1, c, 1); // 세로 
		dfs(r + 1, c + 1, 2); // 대각선
	}
	else { // 대각선
		dfs(r, c + 1, 0); // 가로
		dfs(r + 1, c, 1); // 세로 
		dfs(r + 1, c + 1, 2); // 대각선
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	dfs(1, 2, 0);
	cout << ans;
}

 

Java

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

public class Main {
	
	static final int WALL = 1;
	
	static int N;
	static int ans=0;
	static int home[][];
	
	public static void main(String[] args) throws Exception {
		
		// System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		home = new int[N][N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				home[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dfs(0, 1, 0);
		System.out.println(ans);
	}

	private static void dfs(int y, int x, int d) {
		if(y>=N || x>=N || home[y][x]==WALL) return;
		if(d==2 && (home[y-1][x]==WALL || home[y][x-1]==WALL)) return;
		if(y==N-1 && x==N-1) { // 파이프를 이동을 완료한 경우
			ans++;
			return;
		}
		if(d ==0) { // 가로 
			dfs(y, x+1, 0);
			dfs(y+1, x+1, 2);			
		}
		else if(d==1) { // 세로 
			dfs(y+1, x, 1);
			dfs(y+1, x+1, 2);
		}
		else if(d==2) { // 대각선 
			dfs(y, x+1, 0);
			dfs(y+1, x, 1);
			dfs(y+1, x+1, 2);
		}
	}
}