#백준_17070 파이프 옮기기1 - Java 자바

# 유형 : 브루트 포스, 그래프 탐색

# 난이도 : 골드 V

# 브루트 포스 문제인데, BFS로 접근해서 해결하려다 테스트케이스와 같이 답은 나오지만 시간초과가 났다. 그래서 검색을 해봤더니

***BFS는 같은 정점을 한 번 방문해야 하는데, 같은 정점을 여러 번 방문하는 BFS와 같은 소스가 많습니다.

이건 브루트 포스를 Queue를 이용해서 BFS처럼 구현한 것입니다.*** 라고 하였다. 따라서 그냥 재귀함수로 해결하였다.

 

팁

1. 가로로 놓여져있는 경우 세로로 못간다. <-> 세로도 가로로 못간다.

2. 범위를 벗어나거나 벽이면 못간다.

3. 대각선으로 이동시에 오른쪽 또는 아래가 막혀있으면 못간다.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p17070 {
    static int N, result = 0;
    static int arr[][];
    static int moveX[] = {1,0,1};
    static int moveY[] = {0,1,1};
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
//        bfs();
        solve(2,1,0);
        System.out.println(result);
    }
    
    private static void solve(int x, int y, int what) {
        // TODO Auto-generated method stub
        if(x == N && y == N) {
            result++;
            return;
        }
        for(int d=0; d<3; d++) {
            
            int newY = y + moveY[d];
            int newX = x + moveX[d];
            
            // 가로인 상황에서 세로로 이동 불가능 <->세로에서 가로도 불가능
            if((d==1 && what==0) || (d==0 && what==1))
                continue;
            
            // 범위를 벗어나거나 벽일때
            if(newY > N || newX > N || arr[newY][newX] ==1)
                continue;
            
            // 대각선인데 오른쪽 또는 아래가 벽이 있는 경
            if(d==2 && (arr[y][x+1]==1 || arr[y+1][x] ==1))
                continue;
            
            solve(newX,newY,d);
        }
    }
 
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Po> queue = new LinkedList<>();
        queue.add(new Po(2,1,0));
        
        while(!queue.isEmpty()) {
            Po p = queue.poll();
            if(p.x == N && p.y == N) {
                result++;
                continue;
            }
            
            for(int d=0; d<3; d++) {
                
                int newX = p.x + moveX[d];
                int newY = p.y + moveY[d];
                
                if((d==1 && p.what==0) || (d==0 && p.what==1))
                    continue;
                
                if(newY > N || newX > N || arr[newY][newX] ==1)
                    continue;
                
                if(d==2 && (arr[p.y][p.x+1]==1 || arr[p.y+1][p.x] ==1))
                    continue;
                
                queue.add(new Po(newX, newY, d));
            }
        }
    }
    public static class Po{
        int x;
        int y;
        int what;
        public Po(int x, int y, int what) {
            this.x=x;
            this.y=y;
            this.what=what;
        }
    }
}