[BOJ][JAVA] 17070번: 파이프 옮기기 1

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

푸는 동안 사고과정 및 개선점

dfs를 사용했고, 처음에 구상한대로 잘 풀려서 기분 좋았던 문제.

좌표를 i, j 값 따로 넘기지 않고 new int[]{i,j} 형태로 크기 2짜리 int배열 좌표 객체를 만들어서 넘겼더니 메모리를 엄청 사용했다. 

---

정답코드

우선 메모리를 엄청 잡아먹은 코드 먼저 보겠다. 근데 사실 new int[]{i, j} 코드를 그냥 분리시킨거라서 동일한 코드다. 처음에는 방문체크를 해야될 줄 알고 visited도 만들었는데 이전으로 돌아가는 경우가 없어서 방문 처리는 필요하지않았다. 

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

public class Main {
	static int n;
	static int[][] map;
	static boolean[][] v;
	static int find;
	static int state; // 0,1,2

	public static void dfs(int cs, int[] next) {
		int ci = next[0];
		int cj = next[1];
		if (ci == n - 1 && cj == n - 1) {
			find++;
			return;
		}
		if (cs == 0) {// 이전 상태가 가로. 다음길은 0,1 만 보면됨.
			// 0
			if (cj < n - 1 && map[ci][cj + 1] == 0) {
				dfs(0, new int[] { ci, cj + 1 });
			}
			// 1
			if (cj < n - 1 && ci < n - 1 && map[ci + 1][cj + 1] == 0 && map[ci][cj + 1] == 0 && map[ci + 1][cj] == 0) {
				dfs(1, new int[] { ci + 1, cj + 1 });
			}
		}
		if (cs == 1) {// 다음길은 0,1,2 보면됨.
			// 0
			if (cj < n - 1 && map[ci][cj + 1] == 0) {
				dfs(0, new int[] { ci, cj + 1 });
			}
			// 1
			if (cj < n - 1 && ci < n - 1 && map[ci + 1][cj + 1] == 0 && map[ci][cj + 1] == 0 && map[ci + 1][cj] == 0) {
				dfs(1, new int[] { ci + 1, cj + 1 });
			}
			// 2
			if (ci < n - 1 && map[ci + 1][cj] == 0) {
				dfs(2, new int[] { ci + 1, cj });
			}
		}
		if (cs == 2) {// 다음길은 1,2 보면됨.
			// 1
			if (cj < n - 1 && ci < n - 1 && map[ci + 1][cj + 1] == 0 && map[ci][cj + 1] == 0 && map[ci + 1][cj] == 0) {
				dfs(1, new int[] { ci + 1, cj + 1 });
			}
			// 2
			if (ci < n - 1 && map[ci + 1][cj] == 0) {
				dfs(2, new int[] { ci + 1, cj });
			}
		}
	}

	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		v = new boolean[n][n];
		find = 0;
		state = 0; // 0,1,2 -> 가로 대각 세로
		StringTokenizer st = null;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// 0,0 이랑 0,1 은 이미 방문처리 된거고 시작지점이 0,1부터
		v[0][0] = true;
		v[0][1] = true;
		dfs(0, new int[] { 0, 1 });
		System.out.println(find);
	}
}

 

그리고 이 코드가 좌표를 분리시킨 코드

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

public class Main {
    static int n;
    static int[][] map;
    static int find;

    public static void dfs(int ci, int cj, int cs) {
        if (ci == n - 1 && cj == n - 1) {
            find++;
            return;
        }

        if (cs == 0) {
            if (cj < n - 1 && map[ci][cj + 1] == 0) {
                dfs(ci, cj + 1, 0);
            }
            if (cj < n - 1 && ci < n - 1 && map[ci + 1][cj + 1] == 0 && map[ci][cj + 1] == 0 && map[ci + 1][cj] == 0) {
                dfs(ci + 1, cj + 1, 1);
            }
        } else if (cs == 1) {
            if (cj < n - 1 && map[ci][cj + 1] == 0) {
                dfs(ci, cj + 1, 0);
            }
            if (cj < n - 1 && ci < n - 1 && map[ci + 1][cj + 1] == 0 && map[ci][cj + 1] == 0 && map[ci + 1][cj] == 0) {
                dfs(ci + 1, cj + 1, 1);
            }
            if (ci < n - 1 && map[ci + 1][cj] == 0) {
                dfs(ci + 1, cj, 2);
            }
        } else if (cs == 2) {
            if (cj < n - 1 && ci < n - 1 && map[ci + 1][cj + 1] == 0 && map[ci][cj + 1] == 0 && map[ci + 1][cj] == 0) {
                dfs(ci + 1, cj + 1, 1);
            }
            if (ci < n - 1 && map[ci + 1][cj] == 0) {
                dfs(ci + 1, cj, 2);
            }
        }
    }

    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];
        find = 0;
        StringTokenizer st = null;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 1, 0); // 시작 위치 설정
        System.out.println(find);
    }
}

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^