링크

17070 파이프 옮기기1

문제

풀이

이 문제는 dfs로 완탐 구현 문제이다.
나는 대각선 파이프가 3칸 잡아먹는지 모르고 풀다가 자꾸 안풀려서 처음부터 다시 짰다 ㅜㅜ
로직은
1. 대각선상태라면 가로, 세로, 대각선 3개 다 가능하다
2. 가로상태라면 가로, 대각선 2개 가능하다
3. 세로상태라면 세로, 대각선 2개 가능하다
이것만 주의해서 풀면 어려운 것은 없었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	//가로 세로 대각선
	public static int[] dx = {0, 1, 1};
	public static int[] dy = {1, 0, 1};
	public static int[][] map;
	public static boolean[][] visited;
	public static int n;
	public static int count = 0;
	
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		visited = new boolean[n][n];
		
		for(int i=0;i<n;i++) {
			String[] arr = br.readLine().split(" ");
			
			for(int j=0;j<arr.length;j++) {
				map[i][j] = Integer.parseInt(arr[j]);
			}
		}
		
		
		dfs(0, 1, 0);
		System.out.println(count);
		
	}
	
	//가로 세로 대각선
	public static void dfs(int x, int y, int direction) {
		if(x == n-1 && y == n-1) {
			count++;
			return;
		}
		
		
		//가로
		if(direction == 0) {
			if(checkSameWay(x, y, direction)) dfs(x + dx[direction], y + dy[direction], direction);
			if(checkThreeWay(x, y)) dfs(x + dx[2], y + dy[2], 2);
		} else if(direction == 1) {
			if(checkSameWay(x, y, direction)) dfs(x + dx[direction], y + dy[direction], direction);
			if(checkThreeWay(x, y)) dfs(x + dx[2], y + dy[2], 2);
		} else {
			if(checkSameWay(x, y, 0)) dfs(x + dx[0], y + dy[0], 0);
			if(checkSameWay(x, y, 1)) dfs(x + dx[1], y + dy[1], 1);
			if(checkThreeWay(x, y)) dfs(x + dx[direction], y + dy[direction], 2);
			
		}
		
		
	}
	
	
	public static boolean checkThreeWay(int x, int y) {
		
		for(int i=0;i<3;i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			
			if(newX < 0 || newY < 0 || newX >= map.length || newY >= map[0].length || map[newX][newY] == 1)
				return false;
		}
		
		
		return true;
	}
	
	public static boolean checkSameWay(int x, int y, int direction) {
		
		int newX = x + dx[direction];
		int newY = y + dy[direction];
		
		if(newX < 0 || newY < 0 || newX >= map.length || newY >= map[0].length || map[newX][newY] == 1)
			return false;
		
		
		return true;
	}
}