해당 문제는 특정 목적지까지 특정조건(사탕을 최대한 많이 가지도록)을 만족하면서 가는 길을 찾는 문제이다.
아이디어
문제를 보는 순간, 최적화된 경로를 찾는 문제의 한 종류이므로, BFS 나 DFS를 사용할 것이라 생각했다.
그리고 현재의 최선의 선택이 최종적으로 최선의 선택이 된다는 보장이 없으므로 그리디 알고리즘은 아니라고 생각했고 따라서 DFS가 아닌 BFS를 선택했다.
BFS 풀이 (틀린풀이)
(1,1) 에서 시작해서 (n,m)까지 이동해야 한다.
- (1,1)를 Q.add() 하고 while loop를 실행한다.
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(1,1));
while(!q.isEmpty()){
}- 이동 가능한 선택지를 선택한 후
for (int i = 0; i < 3; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (!check(nx,ny)){ // 이동불가능한 것들은 패스
continue;
}
}- 해당위치의 dp값과 이동가능한 경로의 dp 값을 비교한 후 최신화한다. 만약 최신화가 되었다면 Q.add() 해준다.
if (dp[nx][ny] < dp[cur.x][cur.y]+board[nx][ny]){
dp[nx][ny] = dp[cur.x][cur.y]+board[nx][ny];
q.add(new Pair(nx,ny));
}- dp[n][m]을 출력한다.
System.out.println(dp[n][m]);총 BFS 코드
final static int MAX = 1000+2;
static int n;
static int m;
static class Pair
{
private int x;
private int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
public boolean check(int x,int y){
return x <= n
&& x > 0
&& y <= m
&& y > 0;
}
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
n = Integer.parseInt(split[0]);
m = Integer.parseInt(split[1]);
int[][] board = new int[MAX][MAX];
int[][] dp = new int[MAX][MAX];
for (int i = 1; i <= n; i++) {
String[] split1 = br.readLine().split(" ");
for (int j = 1; j <= m; j++) {
board[i][j] = Integer.parseInt(split1[j - 1]);
dp[i][j]=board[i][j];
}
}
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(1,1));
int[] dx = {1,0,1};
int[] dy = {0,1,1};
while(!q.isEmpty()){
Pair cur = q.remove();
// move 이동, 상태변경, 가능한 것들 큐에 추가
for (int i = 0; i < 3; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (!check(nx,ny)){ // 이동불가능한 것들은 패스
continue;
}
if (dp[nx][ny] < dp[cur.x][cur.y]+board[nx][ny]){
dp[nx][ny] = dp[cur.x][cur.y]+board[nx][ny];
q.add(new Pair(nx,ny));
}
}
}
System.out.println(dp[n][m]);
}해당풀이 반례
하지만 해당 풀이는 반례가 존재한다. dp값이 최신화 될때만 Q.add()가 진행된다는 점이다.
해당 풀이는 처음에 dp값에 설탕개수를 넣고 시작하므로 그 값이 최대로 크다면, 해당 지점은 한번도 최신화가 진행되지 않게된다. 반례는 다음과 같다.
3 3
0 0 0
0 0 0
0 10 0반례를 해결하기 위한 시도
- <=
기존 0이었던 지점이 이후 0이 될때 문제가 발생했다.
따라서 위 풀이의 3번지점에 등호를 추가했다.
if (dp[nx][ny] <= dp[cur.x][cur.y]+board[nx][ny]){
dp[nx][ny] = dp[cur.x][cur.y]+board[nx][ny];
q.add(new Pair(nx,ny));
}결과 : 메모리초과
이유 : 같은지점에 여러번 Q.add()가 발생할 수 있으므로 계속 중복되어 최종 2^2000까지의 경우의 수가 발생한다.
- ||
0인 지점에서 최신화가 발생하지 않는 버그가 문제이므로 || 조건으로 0을 추가해줬다.
if (dp[nx][ny] < dp[cur.x][cur.y]+board[nx][ny]
|| dp[cur.x][cur.y]==0)결과 : 메모리초과
이유 : 위 동일
- visited
0에 초점을 맞추지 않고, 한번도 최신화가 발생하지 않는 지점이 문제이므로 한번도 방문되지 않은 지점에 접근할때는 무조건 방문하도록 조건을 수정했다.
if (dp[nx][ny] < dp[cur.x][cur.y]+board[nx][ny]
|| visited[nx][ny]==0)결과 : correct
맺으며
조건이 있는 방문에서 visitied를 사용하지 않으면 방문하지 않는 지점이 생길 수 있다.
따라서 방문되지 않는 노드가 생기면 안될경우 visited 변수를 추가해야 한다.
최종코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import static java.lang.Math.max;
public class Main {
final static int MAX = 1000+2;
static int n;
static int m;
static class Pair
{
private int x;
private int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
public boolean check(int x,int y){
return x <= n
&& x > 0
&& y <= m
&& y > 0;
}
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
n = Integer.parseInt(split[0]);
m = Integer.parseInt(split[1]);
int[][] board = new int[MAX][MAX];
int[][] dp = new int[MAX][MAX];
for (int i = 1; i <= n; i++) {
String[] split1 = br.readLine().split(" ");
for (int j = 1; j <= m; j++) {
board[i][j] = Integer.parseInt(split1[j - 1]);
dp[i][j]=board[i][j];
}
}
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(1,1));
int[] dx = {1,0,1};
int[] dy = {0,1,1};
int[][] visited = new int[MAX][MAX];
while(!q.isEmpty()){
Pair cur = q.remove();
// move 이동, 상태변경, 가능한 것들 큐에 추가
for (int i = 0; i < 3; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (!check(nx,ny)){ // 이동불가능한 것들은 패스
continue;
}
if (dp[nx][ny] < dp[cur.x][cur.y]+board[nx][ny]
|| visited[nx][ny]==0){
dp[nx][ny] = max(dp[cur.x][cur.y]+board[nx][ny],dp[nx][ny]);
q.add(new Pair(nx,ny));
}
}
}
System.out.println(dp[n][m]);
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
/*
1. 배열을 입력받는다.
dp를 세팅한다
조건1 : 증가하는 함수
조건2 : dp값이 제일 크도록
이전에 나보다 작은 수를 찾아서
each : dp[i] = max(dp[i], dp[k]+arr[i])
*/