[백준] 4485 녹색 옷 입은 애가 젤다지?

4485번: 녹색 옷 입은 애가 젤다지?

 

www.acmicpc.net

풀이

경주로 건설 문제와 거의 유사한 문제이다. BFS 알고리즘을 통해서 해결했다. 주의해야할 것은 같은 지점에 위치할 때의 루피의 값이 이전 방향에 따라서 달라질 수 있다는 것이다. BFS외에 다익스트라 알고리즘을 통해서도 해결할 수 있다.

코드

C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 987654321
using namespace std;

struct Link {
    int x, y, dir;
};

int map[125][125];
int chk[125][125][4];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

void init(int size) {
    for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++) 
            for (int k = 0; k < 4; k++)
                chk[i][j][k] = MAX;        
}

int bfs(int size) {
    init(size);
    queue<Link> q;
    for (int i = 0; i < 4; i++) {
        chk[0][0][i] = map[0][0];
        q.push({ 0, 0, i });
    }

    while (!q.empty()) {
        Link cur = q.front();
        q.pop();

        int x = cur.x;
        int y = cur.y;
        int dir = cur.dir;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx > size - 1 || ny < 0 || ny > size - 1) continue;
            if (chk[ny][nx][i] > chk[y][x][dir] + map[ny][nx]) {
                chk[ny][nx][i] = chk[y][x][dir] + map[ny][nx];
                q.push({ nx, ny, i });
            }
        }
    }

    int ret = MAX;
    for (int i = 0; i < 4; i++) ret = min(ret, chk[size - 1][size - 1][i]);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    while (true) {
        int size;
        cin >> size;
        if (size == 0) break;

        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                cin >> map[i][j];
        cout << "Problem " << t++ << ": " << bfs(size) << '\n';
    }
    return 0;
}

Java

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Link {
    int x, y, dir;

    public Link(int x, int y, int dir) {
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
}

public class Main {
    static int[][] map;
    static int[][][] chk;
    static final int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};

    public static int bfs(int size) {
        Queue<Link> q = new LinkedList<>();
        for (int i = 0; i < 4; i++) {
            q.add(new Link(0, 0, i));
            chk[0][0][i] = map[0][0];
        }

        while (!q.isEmpty()) {
            Link cur = q.poll();
            int x = cur.x, y = cur.y, dir = cur.dir;

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if (nx < 0 || nx >= size || ny < 0 || ny >= size) continue;

                if (chk[y][x][dir] + map[ny][nx] < chk[ny][nx][i]) {
                    chk[ny][nx][i] = chk[y][x][dir] + map[ny][nx];
                    q.add(new Link(nx, ny, i));
                }
            }
        }
        int ret = Integer.MAX_VALUE;
        for (int i = 0; i < 4; i++) ret = Integer.min(ret, chk[size - 1][size - 1][i]);
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int t = 1;
        while (true) {
            int size = Integer.parseInt(br.readLine());
            if (size == 0) break;

            map = new int[size][size];
            chk = new int[size][size][4];
            for (int i = 0; i < size; i++)
                for (int j = 0; j < size; j++)
                    for (int k = 0; k < 4; k++)
                        chk[i][j][k] = Integer.MAX_VALUE;

            for (int i = 0; i < size; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < size; j++)
                    map[i][j] = Integer.parseInt(st.nextToken());
            }
            int answer = bfs(size);
            bw.write("Problem " + t++ + ": " + answer + "\n");
            bw.flush();
        }
    }
}