[BOJ 17070] 파이프 옮기기 1 (Java)

문제

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

17070번: 파이프 옮기기 1

 

풀이

1. 진출 방향에 따른 x, y 좌표 증가분을 미리 정의해 둔다. 

2. 현재 파이프의 방향에 따라 진출 가능한 방향을 미리 정의해둔다. 

    static HashMap<Character, int[]> dir = new HashMap<Character, int[]>(){{
        put('V', new int[]{1, 0});
        put('H', new int[]{0, 1});
        put('D', new int[]{1, 1});
    }};
    static HashMap<Character, List<Character>> possibleDir = new HashMap<Character, List<Character>>(){{
        put('V', Arrays.asList('V', 'D'));
        put('H', Arrays.asList('H', 'D'));
        put('D', Arrays.asList('V', 'H', 'D'));
    }};

 

3. dfs 를 진행한다. 

좌표가 N, N일 때 count를 증가시킨다. 

현재 좌표와 방향을 받아서 다음 진출 방향과 좌표를 계산한다. 

해당 좌표로 진출 가능한지 체크한 후, 가능하다면 탐색을 계속 진행한다.

    public static void dfs(int x, int y, char cur){
        if(x == N && y == N){
            answer++;
            return;
        }
        for(char nDir : possibleDir.get(cur)){
            int nx = x + dir.get(nDir)[0];
            int ny = y + dir.get(nDir)[1];
            if(isValid(nx, ny, nDir)){
                dfs(nx, ny, nDir);
            }
        }
    }

 

4. isValid 코드

범위 내 좌표인지 체크한다. 

대각선의 경우 대각선 방향과 오른쪽, 아래쪽 방향 모두 벽이 없어야 한다. 

가로, 세로는 진출 좌표에 대해서만 벽 체크를 한다.

    public static boolean isValid(int nx, int ny, char nDir){
        if(nx < 1 || ny < 1|| nx > N || ny > N) return false;
        if(nDir == 'D'){
            if(map[nx][ny] == 0 && map[nx][ny-1] == 0 && map[nx-1][ny] == 0) return true;
        } else {
            if (map[nx][ny] == 0) return true;
        }
        return false;
    }

 

소스코드

package dfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ17070 {

    static HashMap<Character, int[]> dir = new HashMap<Character, int[]>(){{
        put('V', new int[]{1, 0});
        put('H', new int[]{0, 1});
        put('D', new int[]{1, 1});
    }};
    static HashMap<Character, List<Character>> possibleDir = new HashMap<Character, List<Character>>(){{
        put('V', Arrays.asList('V', 'D'));
        put('H', Arrays.asList('H', 'D'));
        put('D', Arrays.asList('V', 'H', 'D'));
    }};

    static int N, answer;
    static int[][] map;
    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+1][N+1];
        StringTokenizer st = null;
        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(1, 2, 'H');
        System.out.println(answer);
    }

    public static void dfs(int x, int y, char cur){
        if(x == N && y == N){
            answer++;
            return;
        }
        for(char nDir : possibleDir.get(cur)){
            int nx = x + dir.get(nDir)[0];
            int ny = y + dir.get(nDir)[1];
            if(isValid(nx, ny, nDir)){
                dfs(nx, ny, nDir);
            }
        }
    }

    public static boolean isValid(int nx, int ny, char nDir){
        if(nx < 1 || ny < 1|| nx > N || ny > N) return false;
        if(nDir == 'D'){
            if(map[nx][ny] == 0 && map[nx][ny-1] == 0 && map[nx-1][ny] == 0) return true;
        } else {
            if (map[nx][ny] == 0) return true;
        }
        return false;
    }
}