문제 이해 단계
https://www.acmicpc.net/problem/4485
4485번: 녹색 옷 입은 애가 젤다지?
젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주
www.acmicpc.net
NxN 2차원 맵이 주어진다.
각 칸에는 0 ~ 9까지에 정수가 적혀있다.
그리고 각 칸을 밟을 때마다 해당 점수를 얻는다.
점수를 최대한 적게 얻으면서 (0,0)에서
(N-1, N-1)까지 이동하는 것이 목표이다.
플레이어는 상하좌우로 움직일 수 있을 때,
최소 점수를 구하는 것이 문제이다.
문제 접근 단계
문제 조건부터 살펴보면
맵의 크기 N은 최대 125, 즉 125*125 짜리 맵이다.
그렇게까지 크지는 않아서 완전탐색이 가능하다.
그리고 플레이어는 상하좌우로 움직일 수 있다.
사실 2차원 맵에 상하좌우로 움직일 수 있다는 점이
대놓고 그래프 탐색 문제라고 광고하는 것이다.
그래서 나는 그래프 탐색으로 접근했다.
처음에는 DFS로 탐색했다.
어쨌든 최소한의 합을 찾는 것이기 때문에
경로가 중요하다고 생각했기 때문이다.
그런데 재귀함수 호출 때문인지 메모리초과를 해결할 수 없었다.
그걸 해결하니 시간초과가 떴다.
그래서 방법을 바꿔 BFS로 접근하기로 했다.
각 칸에 점수 체크
BFS는 같은 경로를 연속해서 가는 것이 아니기 때문에,
한번 갔던 경로에 대한 값을 저장하는 작업이 필요하다.
나는 이 방법으로 각 칸마다
점수의 합을 저장해 두는 공간을 만들어서 해결했다.
한마디로 맵의 크기와 같은 2차원 배열을
하나 더 만들었다는 소리이다.
이 방법을 사용해서 이동할 때마다
각 구간별로 합의 정보를 저장해 뒀다.
말로 하면 확인하기 힘드니까 그림으로 살펴보자.
문제 예제케이스에서 3x3 짜리 가져왔다.
왼쪽은 입력으로 주어지는 MAP이고
오른쪽은 방문 체크이자 합 정보를 저장해 둘 VISIT 배열이다.
INF는 infinity의 약자로 엄청나게 큰 숫자를 뜻한다.
우리가 찾아야 할 것은 최솟값이기 때문에,
다른 값과 비교할 때 무조건 비교하는 값이 나오도록 이렇게 한 것이다.
항상 시작은 (0,0)이고
끝은 (N-1, N-1) 여기서는 (2,2)로 가야 한다.
먼저 시작할 때는 합이 당연히 0이다.
그러니까 현재값 + map [0][0]은 당연히 0+5 = 5이다.
즉, 5와 INF 중 당연히 큰 것은 5이기 때문에
VISIT [0][0]을 더 작은 값 5로 바꿔준다.
그다음은 (0,0)과 연결된 블록을 보자.
(0,1)로 이동할 때에 현재값은 5이다.
그리고 map [0][1]은 5이다.
즉, 5+5와 INF 중
더 작은 값 10이 VISIT [0][1]의 값이 된다.
마찬가지의 원리로
VISIT [1][0] = 5+3으로 8이 된다.
다음 map [0][1]과 연결된 두 블록을 살펴보자.
똑같은 원리로 14와 19로 초기화된다.
여기까지는 큰 문제가 없다.
문제는 map [1][0]과 연결된 블록을 초기화할 때 발생한다.
이런 식으로 visit [1][1]에서 경쟁이 일어난다.
둘 중에 더 작은 값인 17이 선택된다.
이런 식으로 쭉 초기화되도록 하면 된다.
설명은 충분히 된 것 같으니 이후의 과정은 생략하도록 하겠다.
이제 나머지 부분은 문제 구현 단계에서 살펴보겠다.
문제 구현 단계
int map[126][126] = {0,};
int visited[126][126] = {0,};
int n;
// 좌표 구조체
struct Point{
int x;
int y;
};
void bfs(int sx, int sy){
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
queue<Point> q;
// 시작하는 위치로 초기화
visited[sx][sy] = map[sx][sy];
q.push({sx,sy});
while(!q.empty()){
int x = q.front().x;
int y = q.front().y;
q.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 맵 밖으로 나가는 것 제외
if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
// (현재까지의 합 + 다음 위치 값)이 다음에 이미 저장되어 있는 합보다 크거나 같으면 패스
if(visited[x][y] + map[nx][ny] >= visited[nx][ny]) continue;
visited[nx][ny] = visited[x][y] + map[nx][ny];
q.push({nx,ny}); // 큐에 담아줌
}
}
}핵심 함수인 BFS 함수이다.
여기서 좌표를 좀 더 편하게 보기 위해
Point 구조체를 선언해 줬다.
매개변수로는 시작 좌표를 받았고,
큐에 넣고 bfs를 시작하기 전에
시작 visit좌표에 map [sx][sy]를 넣고 시작했다.
B(현재까지 합한 값+ 다음 좌표에서 더할 값)이
이미 저장되어 있는 값보다 크거나 같다면
필요 없기 때문에 스킵한다.
여기서 중요한 것은 크기가 같아도 패스한다는 것이다.
크기가 같은 것도 중복에 포함되기 때문이다.
여기까지가 핵심 함수이자,
이 문제의 끝이고 이제 아래에 전체 코드에 대해 올리고 끝내겠다.
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int map[126][126] = {0,};
int visited[126][126] = {0,};
int n;
// 좌표 구조체
struct Point{
int x;
int y;
};
void bfs(int sx, int sy){
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
queue<Point> q;
// 시작하는 위치로 초기화
visited[sx][sy] = map[sx][sy];
q.push({sx,sy});
while(!q.empty()){
int x = q.front().x;
int y = q.front().y;
q.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 맵 밖으로 나가는 것 제외
if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
// (현재까지의 합 + 다음 위치 값)이 다음에 이미 저장되어 있는 합보다 크거나 같으면 패스
if(visited[x][y] + map[nx][ny] >= visited[nx][ny]) continue;
visited[nx][ny] = visited[x][y] + map[nx][ny];
q.push({nx,ny}); // 큐에 담아줌
}
}
}
int main(){
int num = 1;
while(true){
scanf("%d",&n);
if(n == 0) break; // 0이 들어오면 종료
for(int i = 0; i < 126; i++)
for(int j = 0; j < 126; j++) {
visited[i][j] = 9999; // visited을 INF로 초기화
map[i][j] = 0;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) scanf("%d",&map[i][j]);
bfs(0,0);
printf("Problem %d: %d\n",num,visited[n-1][n-1]);
num++;
}
}
시행착오
이거 왜 못 풀었지..
충분히 풀 수 있었던 문제인데
DFS로 시작했던 게 잘못된 선택이었던 것 같다.
이거 보니까 다익스트라로도 풀던데
0~9 사이라서 그렇게 풀 수 있다고 하더라.
음 다익스트라도 공부하긴 해야겠다.
BFS로 하다가 중간에 틀었는데 괜히 틀었네..
다음엔 꼭 맞춰야지