BOJ_17070_파이프 옮기기1

1.

구분: 그래프 탐색, 다이나믹프로그래밍
언어: Java
전략:

• Point class 생성 - 파이프의 좌표를 담기 위한 class
• 재귀 함수에는 시작점을 가지는 Point, 끝점을 가지는 Poin를 매개변수로 가진다.
• 파이프의 방향 찾기 - 가로 파이프: x좌표만 1증가 / 세로 파이프: y좌표만 1증가 / 대각선 파이프: x, y좌표 모두 1 증가
• 각 파이프마다 다음 가능한 방향에 대해서 조건을 맞는다면 기존의 끝점을 시작점으로 해서 재귀를 호출한다. 
• 끝점이 최종 목적지에 도달하면 cnt를 1 증가한다.

---

2. 코드

import java.util.Scanner;

public class BOJ_17070 {
	static class Point{
		int x, y; 
		Point(int y, int x){
			this.x = x;
			this.y = y;
		}
	}
	static int n, cnt;
	static int[][] map;
	static Point next;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		n = scanner.nextInt();
		map = new int[n][n];
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				map[i][j] = scanner.nextInt();
			}
		}
		
		Point start = new Point(0,0);
		Point end = new Point(0,1);
		
		cnt = 0;
		pipe(start, end);
		
		System.out.println(cnt);
		
		
	}//main

	
	private static void pipe(Point start, Point end) {
		//도착했어
		if(end.x == n-1 && end.y == n-1) {
			cnt++;		
			return;
		}
		
		
		//파이프가 가로
		if(end.x-start.x == 1 && end.y-start.y==0) {
			//가로로가 - y, x+1
			//범위 체크 & 벽인가 체크 
			if(end.x+1>=0 && end.y>=0&&end.x+1 < n &&end.y< n 
					&& map[end.y][end.x+1]!=1) {
				next = new Point(end.y, end.x+1);
				pipe(end, next);
			}
			
			
			//대각선
			if(end.x+1>=0 && end.y+1>=0&&end.x+1< n &&end.y+1< n
					&&map[end.y+1][end.x+1] != 1 && map[end.y+1][end.x]!=1 &&
					map[end.y][end.x+1]!=1) {
				next = new Point(end.y+1, end.x+1);
				pipe(end, next);
			}
			
		}
		
		//파이프가 세로
		if(end.x-start.x == 0 && end.y-start.y==1) {
			
			
			//대각선
			if(end.x+1>=0 && end.y+1>=0&&end.x+1< n &&end.y+1< n
					&&map[end.y+1][end.x+1] != 1 && map[end.y+1][end.x]!=1 &&
					map[end.y][end.x+1]!=1) {
				next = new Point(end.y+1, end.x+1);
				pipe(end, next);
			}
			
			//세로 
			if(end.x>=0 && end.y+1>=0&&end.x< n &&end.y+1< n
					&&map[end.y+1][end.x]!=1) {
				next = new Point(end.y+1, end.x);
				pipe(end, next);	
			
				}
			
		}
		
		//파이프가 대각선
		if(end.x-start.x == 1 && end.y-start.y==1) {
			
			//가로
			if(end.x+1>=0 && end.y>=0&&end.x+1 < n &&end.y< n 
					&& map[end.y][end.x+1]!=1) {
				next = new Point(end.y, end.x+1);
				pipe(end, next);
			}
			
			
			//세로 
			if(end.x>=0 && end.y+1>=0&&end.x< n &&end.y+1< n
					&&map[end.y+1][end.x]!=1) {
				next = new Point(end.y+1, end.x);
				pipe(end, next);	
			
				}
			
			//대각선
			if(end.x+1>=0 && end.y+1>=0&&end.x+1< n &&end.y+1< n
					&&map[end.y+1][end.x+1] != 1 && map[end.y+1][end.x]!=1 &&
					map[end.y][end.x+1]!=1) {
				next = new Point(end.y+1, end.x+1);
				pipe(end, next);
			}
			
		}
		
		
	}//pipe
}

---

3. 

• 처음에는 조건을 만족하지 않으면 다 return을 시키는 방식으로 진행했는데, 그러다 보니  나보다 위에 있는 다른 방향에 대해서 조건이 맞지 않는 경우 return이 되어서 정작 실행될 부분이 실행되지 않는 문제가 발생하였다. --> 조건을 만족하는 경우만 다음 단계를 실행
• class Point를 굳이 만들 필요가 없다. 그냥 좌표 변수 4개를 이용하자  - 오히려 메모리를 많이 차지하고, 시간도 오래 걸린다.  
• 디피 방법으로는 아직 구현해보지 못하였다