[백준 17070] 파이프 옮기기 1

[문제 바로가기]👇

17070번: 파이프 옮기기 1

 

💡풀이💡

현재 파이프의 방향과 위치에 따라 이동 가능한 곳이 정해져 있음!

• 특별하게 알 수 있는 방법이 없다고 판단했기 때문에 완전 탐색 진행
• 한 방향으로 갈 수 있는 방법을 모두 가고 그 길이 안되면 다시 돌아와서 다음 방향 탐색
  >> dfs

 

1. 입력 받기

	static int N, ans;
	static int[][] map;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		br.close();
}

 

2. DFS를 이용한 완전 탐색

dfs의 파라미터로 현재 파이프의 정보를 넘기면서 파이프를 밀어서 이동할 때마다 파이프의 정보를 갱신한다

현재 파이프의 방향에 따라 이동할 수 있는 방법이 다르기 때문에 가능한 방향으로 모두 이동해보도록 구현

dfs(0,0,0,1,0);
System.out.println(ans);

//startR : 파이프의 시작 r위치, startC : 파이프의 시작 c위치, endR : 파이프의 끝 r위치, endC : 파이프의 끝 c위치
//dir : 파이프의 방향
static void dfs(int startR, int startC, int endR, int endC, int dir) {
		if(endR==N-1 && endC==N-1) { // 파이프가 끝에 도달했다면
			ans++;
			return;
		}
		
		// 파이프가 현재 가로방향이면
		if(dir==0) {
			//오른쪽으로 이동
			if(endC+1<N && map[endR][endC+1]!=1) {
				dfs(startR, startC+1, endR, endC+1, 0);
			}
			
			//오른쪽 아래 대각선으로 이동
			if(endR+1<N && endC+1<N) {
				if(map[endR+1][endC]!=1 && map[endR][endC+1]!=1 && map[endR+1][endC+1]!=1)
					dfs(startR, startC+1, endR+1, endC+1, 2);
			}
		}
		// 파이프가 현재 세로방향이면
		else if(dir==1) {
			//아래로 이동
			if(endR+1<N && map[endR+1][endC]!=1) {
				dfs(startR+1, startC, endR+1, endC, 1);
			}
			
			//오른쪽 아래 대각선으로 이동
			if(endR+1<N && endC+1<N) {
				if(map[endR+1][endC]!=1 && map[endR][endC+1]!=1 && map[endR+1][endC+1]!=1)
					dfs(startR+1, startC, endR+1, endC+1, 2);
			}
		}
		// 파이프가 현재 대각선방향이면
		else if(dir==2) {
			//오른쪽으로 이동
			if(endC+1<N && map[endR][endC+1]!=1) {
				dfs(startR+1, startC+1, endR, endC+1, 0);
			}
			
			//아래로 이동
			if(endR+1<N && map[endR+1][endC]!=1) {
				dfs(startR+1, startC+1, endR+1, endC, 1);
			}
			
			//오른쪽 아래 대각선으로 이동
			if(endR+1<N && endC+1<N) {
				if(map[endR+1][endC]!=1 && map[endR][endC+1]!=1 && map[endR+1][endC+1]!=1)
					dfs(startR+1, startC+1, endR+1, endC+1, 2);
			}
		}
	}

 

전체 코드

package Day_0329;

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

public class B17070 {
	static int N, ans;
	static int[][] map;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dfs(0,0,0,1,0);
		System.out.println(ans);
		br.close();
	}
	
	//startR : 파이프의 시작 r위치, startC : 파이프의 시작 c위치, endR : 파이프의 끝 r위치, endC : 파이프의 끝 c위치
	//dir : 파이프의 방향
	static void dfs(int startR, int startC, int endR, int endC, int dir) {
		if(endR==N-1 && endC==N-1) { // 파이프가 끝에 도달했다면
			ans++;
			return;
		}
		
		// 파이프가 현재 가로방향이면
		if(dir==0) {
			//오른쪽으로 이동
			if(endC+1<N && map[endR][endC+1]!=1) {
				dfs(startR, startC+1, endR, endC+1, 0);
			}
			
			//오른쪽 아래 대각선으로 이동
			if(endR+1<N && endC+1<N) {
				if(map[endR+1][endC]!=1 && map[endR][endC+1]!=1 && map[endR+1][endC+1]!=1)
					dfs(startR, startC+1, endR+1, endC+1, 2);
			}
		}
		// 파이프가 현재 세로방향이면
		else if(dir==1) {
			//아래로 이동
			if(endR+1<N && map[endR+1][endC]!=1) {
				dfs(startR+1, startC, endR+1, endC, 1);
			}
			
			//오른쪽 아래 대각선으로 이동
			if(endR+1<N && endC+1<N) {
				if(map[endR+1][endC]!=1 && map[endR][endC+1]!=1 && map[endR+1][endC+1]!=1)
					dfs(startR+1, startC, endR+1, endC+1, 2);
			}
		}
		// 파이프가 현재 대각선방향이면
		else if(dir==2) {
			//오른쪽으로 이동
			if(endC+1<N && map[endR][endC+1]!=1) {
				dfs(startR+1, startC+1, endR, endC+1, 0);
			}
			
			//아래로 이동
			if(endR+1<N && map[endR+1][endC]!=1) {
				dfs(startR+1, startC+1, endR+1, endC, 1);
			}
			
			//오른쪽 아래 대각선으로 이동
			if(endR+1<N && endC+1<N) {
				if(map[endR+1][endC]!=1 && map[endR][endC+1]!=1 && map[endR+1][endC+1]!=1)
					dfs(startR+1, startC+1, endR+1, endC+1, 2);
			}
		}
	}

}

 

문제 리뷰

📌놓쳤던 부분

문제에 있는 예제 입력 3번의 답은 0인데 계속 5가 나왔다…

분명 로직에 문제가 있는 건데 어디가 문제인지 몰라서 문제를 다시 읽어보다가 파이프를 이동시킬 때 파이프를 미는 방향에 따라 꼭 빈 칸이어야 하는 곳이 있다는 걸 알게 됐다..😱😱😱😱

 

📌실수했던 부분

파라미터가 많고 조건에 따라 파이프의 시작 위치, 끝 위치를 다 다르게 바꿔줘야 하다보니까

많이 헷갈렸고 한 눈에 안 들어왔다..

그러다보니 이동할 때 파라미터 값을 잘못 넘겨준게 있어서 틀렸었다..

놓친 부분이 아니라 아는데 실수한 거라서 어떻게 보면 더 찾기 힘들었을 것 같은 부분이었다..