[백준] 4485번 : 녹색 옷 입은 애가 젤다지?
문제 푼 날짜 : 2021-07-07
문제
문제 링크 : https://www.acmicpc.net/problem/4485
접근 및 풀이
이전에 풀어본 다익스트라 문제와 달리 배열을 통해 경로를 탐색하며 다익스트라 알고리즘을 적용시켜야 했다. 구현하는데 있어서 크게 다른 점은 없고, BFS를 이용한 문제를 풀때처럼 상하좌우로 배열을 움직일 때 조건을 체크하는 부분이 추가되었다.
최단경로를 저장하는 배열 또한 2차원으로 지정해 주었고, 방문표시를 위한 배열도 선언해주었다.
코드
// 백준 4485번 : 녹색 옷 입은 애가 젤다지?
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321
int N;
int map[126][126];
int visited[126][126];
int dist[126][126];
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { 1, -1, 0, 0 };
void dijkstra() {
priority_queue<pair<int, pair<int, int>>> pq;
pq.push(make_pair(0, make_pair(0, 0)));
visited[0][0] = true;
while(!pq.empty()) {
int y = pq.top().second.first;
int x = pq.top().second.second;
int cost = -pq.top().first;
pq.pop();
for (int i = 0; i < 4; i++) {
int nextY = y + dy[i];
int nextX = x + dx[i];
int nextCost = cost + map[nextY][nextX];
if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N) {
continue;
}
if (visited[nextY][nextX] == false && dist[nextY][nextX] > nextCost) {
dist[nextY][nextX] = nextCost;
visited[nextY][nextX] = true;
pq.push(make_pair(-nextCost, make_pair(nextY, nextX)));
}
}
}
}
int main() {
int num = 1;
while (true) {
cin >> N;
if (N == 0) {
break;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
dist[i][j] = INF;
}
}
memset(visited, false, sizeof(visited));
dijkstra();
cout << "Problem " << num++ << ": " << map[0][0] + dist[N - 1][N - 1] << '\n';
}
return 0;
}
피드백
// 백준 4485번 : 녹색 옷 입은 애가 젤다지?
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321
int N;
int map[126][126];
int visited[126][126];
int dist[126][126];
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { 1, -1, 0, 0 };
void dijkstra() {
priority_queue<pair<int, pair<int, int>>> pq;
pq.push(make_pair(0, make_pair(0, 0)));
visited[0][0] = true;
while(!pq.empty()) {
int y = pq.top().second.first;
int x = pq.top().second.second;
int cost = -pq.top().first;
pq.pop();
for (int i = 0; i < 4; i++) {
int nextY = y + dy[i];
int nextX = x + dx[i];
int nextCost = cost + map[nextY][nextX];
if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N) {
continue;
}
if (visited[nextY][nextX] == false && dist[nextY][nextX] > nextCost) {
dist[nextY][nextX] = nextCost;
visited[nextY][nextX] = true;
pq.push(make_pair(-nextCost, make_pair(nextY, nextX)));
}
}
}
}
int main() {
int num = 1;
while (true) {
cin >> N;
if (N == 0) {
break;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
dist[i][j] = INF;
}
}
memset(visited, false, sizeof(visited));
dijkstra();
cout << "Problem " << num++ << ": " << map[0][0] + dist[N - 1][N - 1] << '\n';
}
return 0;
}
문제에서 배열로 주어지니 처음엔 당황하여 어떻게 해결해야할지 헤매었다.
기본적인 문제말고 좀 더 다양한 유형과 심화문제를 풀어봐야겠다.
Author And Source
이 문제에 관하여([백준] 4485번 : 녹색 옷 입은 애가 젤다지?), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bestcoders/백준-4485번-녹색-옷-입은-애가-젤다지저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)