728x90
다이나믹 프로그래밍... 공부 하고 와야겠다.
8/8
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
static int d[][] = {{0,1}, {1,0}};
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int arr[][] = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(bfs(arr, 0, 0));
}
public static long bfs(int [][]arr, int sRow, int sCol) {
Queue<Point> q = new LinkedList<>();
boolean visited[][] = new boolean[N][N];
q.offer(new Point(sRow, sCol));
visited[sRow][sCol] = true;
long answer = 0;
while (!q.isEmpty()) {
Point cur = q.poll();
for (int i = 0; i < 2; i++) {
int dx = cur.row + d[i][0];
int dy = cur.col + d[i][1];
if (i == 0) {
dy += (arr[cur.row][cur.col] - 1);
} else {
dx += (arr[cur.row][cur.col] - 1);
}
if (dx >= N || dy >= N || visited[dx][dy]) {
continue;
}
if (arr[dx][dy] == 0) {
answer ++;
visited[dx][dy] = false;
}
if (!visited[dx][dy] && arr[dx][dy] != 0) {
q.offer(new Point(dx, dy));
visited[dx][dy] = true;
}
}
}
return answer;
}
static class Point {
int row,col;
public Point(int r, int c) {
this.row = r;
this.col = c;
}
}
}
Queue를 이용한 BFS로 풀어봤으나 하나의 위치에서 오른 쪽으로 가도, 아래로 가도 경로가 될 때 visited 배열로 이미 true가 되어있어서 세지 못 한다.
dp를 이용해야한다.
dp[x][y] = x, y까지 도달할 수 있는 경우의 수 !
이렇게 dp 테이블을 구성해보면
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long dp[][] = new long[N][N];
int arr[][] = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dp[0][0] = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == N - 1 && j == N - 1) {
break;
}
int cnt = arr[i][j];
if (i + cnt < N) {
dp[i + cnt][j] += dp[i][j];
}
if (j + cnt < N) {
dp[i][j + cnt] += dp[i][j];
}
}
}
System.out.println(dp[N - 1][N - 1]);
}
}
정말 간단하게 풀 수 있다 ㅠ 테이블을 어떻게 구성할 지를 잘 떠올려보자 , ,
그리고 for문 중첩으로 입력 받을 때
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(input[j]);
}
}
이렇게 하면 더 간단하게 할 수 있구나 ! 읽어들인 한 줄을 공백으로 구분해서 String형 배열에 넣은 다음에 하나 씩 넣으면 된다 !
'알고리즘 > 백준' 카테고리의 다른 글
(백준/자바) 힌트문제3 05. 그리디 - 백준 11047번 문제 : 동전 0 (0) | 2023.08.06 |
---|---|
(백준/자바) 백준 3273번 문제 : 두 수의 합 (0) | 2023.08.06 |
(백준/자바) 힌트문제3 03. 투 포인터 - 백준 2003번 문제 : 수들의 합2 (0) | 2023.08.06 |
(백준/자바) 힌트문제3 02. 2차원배열 - 백준 2167번 문제 : 2차원 배열의 합 (0) | 2023.08.06 |
(백준/자바) 힌트문제3 01. 팰린드롬 - 백준 1254번 문제 : 팰린드롬 만들기 (0) | 2023.08.06 |