공식힌트 https://tech.kakao.com/posts/339
25.07.10
- 틀림
- 브루트포스하니 시간초과뜸
- DP였다니;
- Think Flow
- 대상을 지점으로 한번 고려해보는거
- 만약 2차원 배열을 떠올렸다면 그 배열 요소가 어떤걸 대상으로 하면 될지 한번 생각해보면 어떨까?
- 어려운 문제;
- 기본적 디피의 응용인거 같긴한데 방향에 따른 경우의수 배열두는것도생소했고 여튼 하드하네;
import java.util.*;
class Solution {
private static final int MOD = 20170805;
private static final int FREE = 0;
private static final int BLOCK = 1;
private static final int GO_STRAIGHT = 2;
public int solution(int m, int n, int[][] cityMap) {
int[][] myCityMap = new int[m+1][n+1];
for(int i=1 ; i<=m ; i++){
for(int j=1 ; j<=n ; j++){
myCityMap[i][j] = cityMap[i-1][j-1];
}
}
//H: i,j에서 오른쪽으로 갈 수 있는 경우의 수
//V: i,j에서 아래쪽으로 갈 수 있는 경우의 수
int[][] H = new int[m+1][n+1];
int[][] V = new int[m+1][n+1];
H[1][1] = 1;
V[1][1] = 1;
//H(오른쪽으로 갈 수 있는 경우의 수)에서는 만약 i,j에서 0(자유)인 경우, 왼쪽, 위쪽 다 가져와도 된다.
//2(회전금지)인 경우에 오른쪽으로가려면 i,j의 왼쪽만 가져와야되구나...!
for(int i=1 ; i<=m ; i++){
for(int j=1 ; j<=n ; j++){
if(i==1 && j==1) continue;
if(myCityMap[i][j] == FREE){
H[i][j] = (H[i][j-1] + V[i-1][j])%MOD;
V[i][j] = (H[i][j-1] + V[i-1][j])%MOD;
}
if(myCityMap[i][j] == BLOCK){
H[i][j] = 0;
V[i][j] = 0;
}
if(myCityMap[i][j] == GO_STRAIGHT){
H[i][j] = H[i][j-1];
V[i][j] = V[i-1][j];
}
}
}
return (H[m][n-1] + V[m-1][n])%MOD;
//return (H[m][n] + V[m][n])%MOD;
}
}import java.util.*;
class Solution {
int MOD = 20170805;
private static int[] di = {-1,0,1,0};
private static int[] dj = {0,1,0,-1};
public int solution(int m, int n, int[][] cityMap) {
//25.07.09
//DFS같은데
//1. 지금 위치전의 이전 방향을 안다.
//2. 그거 기준으로 직진하거나 우회전가능하다.
// 직진하려면 방향+0 하면되고 우회전은 +1 하는걸로 하지.
// di = -1 0 1 0 상 우 하 좌
// dj = 0 1 0 -1 이러면.. 이전에 상방향이었다면 나는 상방향이나 우쪽으로 갈수밖에 없다.
// 이전에 좌방향이었다면 나는 좌방향이나 상방향으로 갈수밖에없다.
//한번 들린곳은 다시 올 수가 없는 상황인 문제
//25.07.10
//아 이거 최단거리 아님; 이거 무슨 최단거릭란말도없는데 뭐냐
// 아 못봣다. 오른쪽 또는 아래방향으로 .....
//틀림 다이나믹이엇다니
int arriveCount = 0;
Queue<JZ> queue = new LinkedList<>();
queue.add(new JZ(0,0,1));
queue.add(new JZ(0,0,2));
cityMap[0][0] = 2;
while(!queue.isEmpty()){
JZ jz = queue.poll();
if(jz.i == cityMap.length-1 && jz.j == cityMap[0].length - 1){
arriveCount = (arriveCount+1)%MOD;
continue;
}
if(cityMap[jz.i][jz.j] == 0){
//방향 그대로 유지
int ni = jz.i + di[jz.preDir];
int nj = jz.j + dj[jz.preDir];
if(ni < cityMap.length && nj < cityMap[0].length){
if(!(cityMap[ni][nj] == 1)){
queue.add(new JZ(ni,nj,jz.preDir));
}
}
//방향이 2(아래)면 오른쪽으로
if(jz.preDir == 2){
ni = jz.i + di[1];
nj = jz.j + dj[1];
if(ni < cityMap.length && nj < cityMap[0].length){
if(!(cityMap[ni][nj] == 1)){
queue.add(new JZ(ni,nj,1));
}
}
}
//방향이 1(오른쪽) 아래로
if(jz.preDir == 1){
ni = jz.i + di[2];
nj = jz.j + dj[2];
if(ni < cityMap.length && nj < cityMap[0].length){
if(!(cityMap[ni][nj] == 1)){
queue.add(new JZ(ni,nj,2));
}
}
}
}
if(cityMap[jz.i][jz.j] == 2){
//방향 그대로 유지
int ni = jz.i + di[jz.preDir];
int nj = jz.j + dj[jz.preDir];
if(ni < cityMap.length && nj < cityMap[0].length){
if(!(cityMap[ni][nj] == 1)){
queue.add(new JZ(ni,nj,jz.preDir));
}
}
}
}
return arriveCount;
}
static class JZ{
int i;
int j;
int preDir;
JZ(int i, int j, int preDir){
this.i = i;
this.j = j;
this.preDir = preDir;
}
}
}