[프로그래머스] 보행자 천국 - 실패

- bfs로 풀려고 시도했으나

- m이 500 으로 크므로 bfs는 최악의 경우에 시간초과가 난다.

- 실패 -> dp로 시도해야 함

 

import java.util.*;
class Point {
    int x;
    int y;
    String dir;
    public Point(int x, int y, String dir) {
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
    
    public String getDir() {
        return dir;
    }
    
    public boolean canMove(int x, int y, int m, int n) {
        return x >=0 && y >= 0 && x < m && y < n;
    }
    
    public boolean isGoal(int m, int n) {
        return x == m-1 && y == n-1;
    }
}
class Solution {
    int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        Queue<Point> q = new LinkedList<Point>();
        q.add(new Point(0, 0, "start"));
        while(!q.isEmpty()) {
            Point cp = q.poll();
            int cx = cp.x;
            int cy = cp.y;
            String dir = cp.dir;
            if(cp.isGoal(m,n)) {
                answer++;
            }
            if(cp.canMove(cx, cy, m, n)) {
                int cVal = cityMap[cx][cy];
                if(cVal == 0) {
                    Point dp = new Point(cx+1, cy, "d");
                    q.add(dp);
                    Point rp = new Point(cx, cy+1, "r");
                    q.add(rp);
                } else if (cVal == 2) {
                    if(dir.equals("d")) {
                        Point dp = new Point(cx+1, cy, "d");
                        q.add(dp);
                    } else if (dir.equals("r")) {
                        Point rp = new Point(cx, cy+1, "r");
                        q.add(rp);
                    }
                } else {
                    // 1일때는 넘어감
                }
            }
        }
        return answer % MOD;
    }
}