[SWEA] 1249 보급로

출처: SWEA

 Input 

2

4

0100

1110

1011

1010

6

011001

010100

010011

101001

010101

111010

 

 Output 

#1 2
#2 2

 

BFS 처리할 때, 재방문 여부를 어떻게 할지 고민할 수 있는 문제입니다.

작업시간만 최소비용이라면 실제 거리는 어떻든 상관 없습니다.

여기서 단순히 BFS의 방문표시하여 재방문하지 않으면 최선의 경로가 탐색되지 않습니다.

 

단순히 방문여부를 확인하는 것이 아니라 해당 지점을

복구 시간이 덜 걸린 경로인지 확인해야 합니다.

①경로로 이미 방문한 곳도 ②경로에서는 작업시간이 덜 걸렸기에

해당 지점에서 재방문 해줘야 합니다.

* 일반적인 BFS에서는 boolean visited[][]로 방문여부를 확인하였다면

   이 문제는 int dist[][]로 복구 시간 정도로 방문여부를 확인.

---

C / C++

#include <stdio.h>

const int MAX_N = 100 + 2;
const int INF = 999999999;
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };

struct Vertex
{
    int x, y, cost;
};
struct Queue {
    int fr, re;
    Vertex arr[MAX_N * MAX_N * MAX_N * 4];

    void init()
    {
        fr = re = 0;
    }

    void push(Vertex data)
    {
        arr[re++] = data;
    }
    Vertex pop()
    {
        return arr[fr++];
    }
    int size()
    {
        return re - fr;
    }

    bool empty()
    {
        return size() == 0 ? true : false;
    }
}q;
int n;
int map[MAX_N][MAX_N], dist[MAX_N][MAX_N];
char str[MAX_N];

int BFS()
{   
    q.init();
    // 처음 출발점(S)에서 시작
    q.push({ 0, 0, 0 });

    while (!q.empty()) {
        Vertex v = q.pop();

        for (int i = 0; i < 4; i++) {
            int nX = v.x + dx[i];
            int nY = v.y + dy[i];

            // 배열 범위를 벗어나는지 확인
            if (nX < 0 || nY < 0 || nX >= n || nY >= n) continue;


            // (현재 탐색에서) 해당 지점까지의 작업시간
            int newCost = v.cost + map[nX][nY];

            // 이미 방문한 곳에서도 시간이 좀 더 단축된 Path인지 확인
            // 이미 다른 경로에서 좀 더 빠르게 도달했다면 굳이 탐색할 필요가 없다.
            if (dist[nX][nY] <= newCost) continue;

            // 해당 지점 방문시간 갱신 (더 오래 걸리는 Path의 방문을 막기 위함)
            dist[nX][nY] = newCost;

            // 계속해서 탐색
            q.push({ nX, nY, newCost });
        }
    }

    return dist[n - 1][n - 1];
}

int main() {
    // freopen("input.txt", "r", stdin);

    int TC; scanf("%d", &TC);
    for (int tc = 1; tc <= TC; ++tc)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            for (int j = 0; j < n; j++) {
                map[i][j] = str[j] - 48;
                // 임의의 큰 수로 초기화
                dist[i][j] = INF;
            }
        }
        printf("#%d %d\n", tc, BFS());
    }
}

 

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Solution {
 
    // 임의의 큰 수
    private static final int INF = 999999999;
    // 상하좌우
    private static int[] dx = { -1, 1, 0, 0};
    private static int[] dy = { 0, 0, -1, 1};
    private static int[][] map, dist;
    private static int n;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        // TestCase
        int tc = Integer.parseInt(sc.next());
        int probNo = 1;
 
 
        while (tc-- > 0) {
            n = Integer.parseInt(sc.next());
            map = new int[n][n];
            dist = new int[n][n];
             
            // 배열 입력
            for(int i=0; i<n; i++) {
                String str = sc.next();
                for(int j=0; j<n; j++) {
                    map[i][j] = str.charAt(j) - '0';
                    // 임의의 큰 수로 초기화
                    dist[i][j] = INF;
                }
            }
             
            // 정답 출력
            System.out.print("#" + (probNo++) + " ");
            System.out.println(BFS());
        }
    }
 
 
    private static int BFS() {
         
        Queue<Vertex> queue = new LinkedList<>();
        // 처음 출발점(S)에서 시작
        queue.offer(new Vertex(0, 0, 0));
         
        while(!queue.isEmpty()) {
            Vertex v = queue.poll();
             
            for(int i=0; i<4; i++) {                
                int nX = v.x + dx[i];
                int nY = v.y + dy[i];
                 
                // 배열 범위를 벗어나는지 확인
                if(nX < 0 || nY < 0 || nX >= n || nY >= n) continue;
                 
                 
                // (현재 탐색에서) 해당 지점까지의 작업시간
                int newCost = v.cost + map[nX][nY];
                 
                // 이미 방문한 곳에서도 시간이 좀 더 단축된 Path인지 확인
                // 이미 다른 경로에서 좀 더 빠르게 도달했다면 굳이 탐색할 필요가 없다.
                if(dist[nX][nY] <= newCost) continue;
                 
                // 해당 지점 방문시간 갱신 (더 오래 걸리는 Path의 방문을 막기 위함)
                dist[nX][nY] = newCost;
                 
                // 계속해서 탐색
                queue.offer(new Vertex(nX, nY, newCost));
            }
        }
         
        return dist[n-1][n-1];
    }
}
 
 
class Vertex {
    int x, y;
    int cost;
     
    public Vertex(int x, int y, int cost) {
        this.x = x;
        this.y = y;
        this.cost = cost;
    }
}