https://www.acmicpc.net/problem/1890
현재 칸에 쓰여진 수만큼 우측이나 하단으로 점프해가며 종착점까지 가는 경우의 수를 센다.
우측이나 하단으로 가므로 원래 위치로 돌아올 일은 없고, 총 경우의 수를 세기 때문에 visited 관리는 필요 X
(좌우상하 다 움직일 수 있었다면 어떻게 해야 했을까?)
1. bfs로 발 닿은 곳마다 방문 횟수를 늘려서 종착점 밟은 수를 모두 세 보자.
2. bfs하면서 나아간 곳의 방문횟수를 이번칸 방문횟수로 업데이트해보자. -> 이럼 종착점에 도달 못한 경우의 수도 합해서 세버리는 경우가 될 듯 한?
메모리초과로 틀린코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class Main {
static int n;
static int[][] arr = new int[101][101];
static long[][] steps = new long[101][101];
static class point{
public int row;
public int col;
public point(int row,int col){
this.row=row;this.col=col;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
for(int i=0;i<n;i++){
String str = br.readLine();
StringTokenizer token = new StringTokenizer(str);
for(int j=0;j<n;j++){
arr[i][j]=Integer.parseInt(token.nextToken());
}
}
ArrayDeque<point> dq = new ArrayDeque<>();
dq.add(new point(0,0));
int[] row ={0,1};
int[] col ={1,0};
while(!dq.isEmpty()){
int len = dq.size();
for(int i=0;i<len;i++){
point p = dq.poll();
steps[p.row][p.col]++;
if(arr[p.row][p.col]==0) continue;
for(int j=0;j<2;j++){
int drow=p.row+row[j]*arr[p.row][p.col];
int dcol=p.col+col[j]*arr[p.row][p.col];
if(drow>=0 && drow<n && dcol>=0 && dcol<n){
dq.add(new point(drow,dcol));
}
}
}
}
System.out.println(steps[n-1][n-1]);
}
}
굳이 bfs를 써야할까? 어차피 우하단으로만 가는데.
전체를 순회하면서 다음에 갈 수 있는 곳의 경우의수를 1씩 더해주자.
상하좌우를 모두 움직일 수 있었더라면 좌우나 위아래로 계속 쌓아주면서 무한까지 갔겠지만
여기선 되돌아갈일이 없잖아.
(DAG인 경우에서는 dp로 풀 수 있다. 효율적)
근데 그렇게 하면 도착점까진 한번에 갈 수 있지만 출발점에서 도달할 수 없는 포인트의 경우까지 추가되는데.
자신의 steps(방문횟수)가 0이면 스킵하도록 하자.
그렇게 구현하면 종착점 직전까지 가는 경로가 여러가지여도 한번만 추가될텐데.
자신의 steps 만큼 더해주도록 하자.
백준 1629 곱셈 (java) (0) | 2024.11.02 |
---|---|
백준 30805 사전 순 최대 공통 부분 수열 (java) (0) | 2024.11.02 |
백준 14889 스타트와 링크(java) (0) | 2024.10.26 |
백준 11000 강의실배정 (C++) (0) | 2024.02.27 |
백준 6603 로또 (c++/백트래킹) (0) | 2024.02.26 |