✨Link 등굣길
🤔 문제
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.
입출력 예 
💡 접근
dfs -> DP 방법을 변경
💻 코드(1)_나의 풀이
static int mm,nn;
static int min,answer;
static int[] dx = {0, 1};
static int[] dy = {1, 0};
static Stack<Node> stack;
static boolean[][] map;
static class Node{
int x,y;
public Node(int x, int y) {
this.x=x;this.y=y;
}
}
public static int solution(int m, int n, int[][] puddles) {
min=Integer.MAX_VALUE;
mm=m;nn=n;
map=new boolean[n][m];
stack=new Stack<>();
//물 구덩이 map->true
for(int i=0;i<puddles.length;i++) {
int x = puddles[i][1];
int y = puddles[i][0];
map[x-1][y-1]=true;
}
stack.add(new Node(0,0));
dfs(0);
return answer;
}
public static void dfs(int cnt) {
while(!stack.isEmpty()) {
Node node=stack.pop();
if(node.x==nn-1&&node.y==mm-1) {
if(min==Math.min(min, cnt)) {
answer++;
}else {
answer=1;
min=cnt;
}
}
for(int i=0;i<2;i++) {
int x=node.x+dx[i];
int y=node.y+dy[i];
if(x>=0 && x<nn && y>=0 && y<mm) {
if(!map[x][y]) {
stack.add(new Node(x,y));
dfs(++cnt);
cnt--;
}
}
}
}
}
}처음 문제를 봤을때, dfs로 풀어야겠다고 생각을 했다. 결과적으로 정확성은 통과했지만 효율성에서 실패를 했다.
진행방향이 오른쪽과 아래로 stack에 담아주었다. 목적지까지 가는데 거리를 cnt변수를 +1해주면서 목적지에 도착했을때, 거리가 최소인지 판별하고 개수를 카운트 해준다. 계속해서 dfs를 부르는 과정때문에 효율성에서 실패를 한것이다..ಥ_ಥ 또한 파라미터로 물웅덩이의 좌표를 받는데 n=세로, m=가로를 반대로 생각하는 바람에 시간이 오래걸렸다..
💻 코드(2)_나의 풀이
public static int solution(int m, int n, int[][] puddles) {
int[][] map = new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(i==0||j==0) {
map[i][j]=1;
}
}
}
//물 웅덩이
for(int i=0;i<puddles.length;i++) {
map[puddles[i][1]-1][puddles[i][0]-1]=-1;
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(map[i][j]==0) {
if(map[i-1][j]!=-1) {
map[i][j]+=map[i-1][j];
}
if(map[i][j-1]!=-1) {
map[i][j]+=map[i][j-1];
}
}
}
}
return map[n-1][m-1];
}
테스트 케이스 1,9,10번을 통과하지 못했다. 풀이는 0행 이거나 0열에 먼저 1로 다 채워 주고 물웅덩이 제외하고 위,왼쪽을 더해서 경우의 수를 찾아내는 방법이었다. 아래의 경우를 생각하지 못한 풀이법이었다..
💻 코드(3)_나의 풀이
public static int solution(int m, int n, int[][] puddles) {
int[][] map = new int[n][m];
//집
map[0][0]=1;
//물 웅덩이
for(int i=0;i<puddles.length;i++) {
map[puddles[i][1]-1][puddles[i][0]-1]=-1;
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(i==0 && j==0) {
continue;
}
if(map[i][j]!=-1) {
if(i-1<0) {
map[i][j]=map[i][j-1];continue;
}
if(j-1<0) {
map[i][j]=map[i-1][j];continue;
}
if(map[i-1][j]==-1 && map[i][j-1]==-1) {
map[i][j]=0;
}else if(map[i-1][j]==-1 || map[i][j-1]==-1) {
map[i][j]=(map[i-1][j]+map[i][j-1]+1)%1000000007;
}else {
map[i][j]=(map[i-1][j]+map[i][j-1])%1000000007;
}
}
}
}
return map[n-1][m-1];
}두번째 풀이처럼 하되, 0행 0열을 1로 채우지 않고 '집' 다음부터 위,왼쪽을 더하면서 경우의 수를 찾았다. 만약 위쪽 위치가 -1이라면 왼쪽만 더해주고, 반대로 왼쪽 위치가 -1이라면 위쪽값만 더해주었다.
🔎 DP(동적계획법): 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
