백준 17070 - 파이프 옮기기 1

Java

17070 번 - 파이프 옮기기 1

문제

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

접근 방법

파이프의 형체는 고려하지 않고, 결국 파이프의 끝이 N, M으로 이동하면 되므로, 시작을 (0,1)로 하여 파이프의 끝 부분을 기준으로 이동을 한다.

각 모양 별로 이동할 수 있는 모든 경우를 재귀함수를 통해 움직인다.

만약 N,M에 도달하면 값을 증가시켜, 도달하는 방법의 개수를 센다.

코드

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

public class Main {
	static int n, result;
	static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	map = new int[n][n];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
    	move(0, 0, 1);
    	System.out.println(result);
    	br.close();
	}

	//type은 현재 파이프가 놓혀진 모양, 0은 가로 / 1은 세로 / 2는 대각
	private static void move(int type, int y, int x) {
		if(y == n - 1 && x == n - 1) {
			result++;
			return;
		}
		
		switch(type) {
		case 0:
			if(isIn(y, x + 1) && map[y][x+1] == 0) {
				move(0,y,x+1);
			}
			if(isIn(y + 1, x + 1) && map[y][x+1] == 0 && map[y+1][x] == 0 && map[y+1][x+1] == 0) {
				move(2,y+1,x+1);
			}
			break;
		case 1:
			if(isIn(y + 1, x) && map[y+1][x] == 0) {
				move(1,y+1,x);
			}
			if(isIn(y + 1, x + 1) && map[y][x+1] == 0 && map[y+1][x] == 0 && map[y+1][x+1] == 0) {
				move(2,y+1,x+1);
			}
			break;
		case 2:
			if(isIn(y, x + 1) && map[y][x+1] == 0) {
				move(0,y,x+1);
			}
			if(isIn(y + 1, x) && map[y+1][x] == 0) {
				move(1,y+1,x);
			}
			if(isIn(y + 1, x + 1) && map[y][x+1] == 0 && map[y+1][x] == 0 && map[y+1][x+1] == 0) {
				move(2,y+1,x+1);
			}
			break;
		}
	}
	
	static boolean isIn(int y, int x) {
		if(y < 0 || y == n || x < 0 || x == n)
			return false;
		return true;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

플로이드 워셜의 응용 문제

개선할 점

없습니다.