문제

너비 우선 탐색(BFS) 알고리즘은 모든 간선의 가중치가 1로 같을 때 최단거리를 찾아줍니다.

1. 택시는 항상 최단 경로로 움직입니다.

2. 만약, 택시로 부터 거리가 가까운 승객이 여러명이라면, 다음 3가지 조건을 모두 비교합니다.

• 1) 가장 가까운 승객
• 2) 행이 가장 작은 승객
• 3) 열이 가장 작은 승객

3. n 지도의 크기 (2 ≤ n ≤ 20)

4. m 승객의 수 (1 ≤ m ≤ n^2)

5. oil 초기 연료 (1 ≤ N ≤ 50만)

6. 지도에서

• 1) 0은 빈칸
• 2) 1은 벽 입니다.

7. 승객을 태우고 도착지점에 도착하면, 태운지점에서 도착지점까지의 거리의 2배의 연료가 충전됩니다.

8. 만약 이동도중에 연료가 부족하면, 종료되고 -1을 출력합니다.

9. 도착지점에 도착하고 0이되는 경우는 부족한것이 아닙니다.

10. 택시와 승객이 같은 위치에 있으면 최단거리는 0입니다.

시간 제한 1초

• 문제 링크

---

1. 첫인상

BFS + 시뮬에이션

• 최단거리를 구하는것에서 BFS

• 절차대로 수행하는것에서 시뮬레이션(구현)이 느껴집니다.

2. 접근 과정

문제를 작게 만들어 보면, 매번 다음을 반복합니다.

1. 택시에서 승객까지의 최단거리를 계산합니다.

• 최단 거리가 같으면 1) 행이 가장 작고, 2) 열이 가장 작은 승객을 찾습니다.
• 연료가 부족한지 검사 해줍니다.
• 사용한 연료를 빼줍니다.

2. 승객의 도착지점을 찾습니다.

3. 승객의 위치에서 도착지점까지의 최단거리를 계산합니다.

• 연료가 부족한지 검사 해줍니다.
• 사용한 연료를 빼줍니다.
• 사용한 연료의 2배를 충전합니다.

크게 3가지의 업무가 있고,

중간 중간 마다 갱신 및 검사가 있습니다.

사실, 대부분의 과정은 일반적인 연산이고.

제일 궁금한것은 2가지 입니다.

1. 최단거리

최단 거리를 어떻게 계산할 수 있나요.

2. 대소 비교

1) 거리가 가장 작고, 2) 행이 가장 작고, 3) 열이 가장 작은 승객을 어떻게 찾을 수 있을까요.

3. 최단 거리

1) BFS

최단 거리 알고리즘에는 1)BFS, 2) 다익스트라, 3) 플로이드 와샬 등등이 있습니다.

다만, 여기서 사용하는 알고리즘은 BFS (너비 우선 탐색) 입니다.

각각의 최단거리 알고리즘에는 사용하는 이유와 사용할 수 있는 조건이 있는데요.

BFS는 모든 간선의 가중치가 1로 같을 때 최단경로를 찾아줍니다.

왜냐하면, 간선의 가중치가 모두 같기 때문에 해당 지점에 가장 먼저 도착하는 경로가 최단경로가 됩니다.

2) 시간 복잡도

너비 우선 탐색(BFS)는 정점을 모두 탐색하는 완전탐색 알고리즘 입니다.

정점의 개수는 n^2 크기의 지도에서 1칸의 개수인 n^2입니다.
그렇기 때문에 BFS의 시간복잡도는 O(n^2)입니다.

3) 택시

택시는 항상 최단 경로로 움직이고, 움직이는 경우는 크게 2가지 입니다.

• 1) 승객을 찾을 때
• 2) 도착지점을 찾을 때

그렇기 때문에, 승객 1명을 태우고 도착지점에 이동시키기 위해서, BFS는 매번 2회 진행하게 됩니다.

4. 대소 비교

1) 거리가 작고, 2) 행이 작고, 3) 열이 작은 승객을 찾는것에는

여러가지 방법이 있는데요, 생각나는대로 적어보면

1) 구조체, if 문 - O(1)

이것은요, 구조체를 사용했다면, if 문 중첩으로 가능합니다.

if (a[nx][ny] == -1) {
    if(check[nx][ny] < person_dist) {
        person_dist = check[nx][ny];
        person_x = nx;
        person_y = ny;
    }
    else if (check[nx][ny] == person_dist) {
        if (nx < person_x) {
            person_dist = check[nx][ny];
            person_x = nx;
            person_y = ny;
        }
        else if (nx == person_x) {
            if (ny < person_y) {
                person_dist = check[nx][ny];
                person_x = nx;
                person_y = ny;
            }
        }
    }
}

2) 구조체, 연산자 오버로딩 - O(1)

구조체를 사용한다면 연산자 오버로딩 사용할 수 있습니다.

코딩 복잡도라는 단위가 있다면 이게 조금 나을 수도 있고요.

// 연산자 오버로딩
// 1) 거리가 작은 순, 2) 행이 작은 순, 3) 열이 작은 순
bool operator < (const info &a, const info &b) {
    if (a.dist == b.dist) {
        if(a.x == b.x) {
            return a.y < b.y;
        }
        else return a.x < b.x;
    }
    else return a.dist < b.dist;
}

// 제일 가까운 승객을 찾아줍니다.
if(next_info < person_info) {
    person_x = nx;
    person_y = ny;
    person_dist = check[nx][ny];
}

3) pair, 비교 - O(1)

c++의 pair를 사용한다면, 2개의 값 행, 열에 대해서는 대소비교를 지원해줍니다.

거리는 다른곳에 저장하고, 행, 열에 대해서만 비교를 해줍니다.

pair<int, int> next_info = make_pair(2, 2);
pair<int, int> person_info = make_pair(2, 3);

if(next_info < person_info) {
    cout << next_info.first << " " << next_info.second << endl;
}

4) 정렬 또는 우선순위 큐 - O(logn)

가능은 한데,

넣을때 마다 logN 씩 걸리니까 .... 일단 시험은 통과하는게 중요하니까 시간안에 가능하다면 오키요

5. 시간 복잡도 계산

m 명의 승객에 대해서 * BFS 2번

BFS 한번에 모든 지도를 완전탐색하기 때문에 BFS의 시간복잡도는 O(n^2)

그래서 m 명의 승객에 대해서 BFS 2번 = 2 m * n^2

상수 생략해서 O(m*n^2)

m 승객의 수(1 ≤ m ≤ n^2) 이니까

O(m*n^2) == O(n^4)

n 지도의 크기 (2 ≤ n ≤ 20) 이니까

20^4 == 160000 (16만)

문제의 시간제한은 1초이고

반복문 1억번 계산하는데 1초걸리기 때문에

O(16만)은 시간이 충분합니다.

6. 전체 코드

1) c++

#include <iostream>
#include <queue>
#define max_int 21
#define max_val 2147483647

/*
    시간 복잡도: m * n^2 (n^4)
    공간 복잡도: n^2
    사용한 알고리즘: BFS - 모든 간선의 가중치가 1로 같을 때 최단거리를 계산합니다.
    사용한 자료구조: 구조체, 2차원 배열
 */

using namespace std;

int n, m, oil, person_cnt, a[max_int][max_int], start_x, start_y, person_x, person_y, target_x, target_y, check[max_int][max_int], person_dist, target_dist;

int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};

// 좌표를 저장하기 위한 구조체
struct info{
    int x, y, dist;
};

// 연산자 오버로딩
// 1) 거리가 작은 순, 2) 행이 작은 순, 3) 열이 작은 순
bool operator < (const info &a, const info &b) {
    if (a.dist == b.dist) {
        if(a.x == b.x) {
            return a.y < b.y;
        }
        else return a.x < b.x;
    }
    else return a.dist < b.dist;
}

// 도착지점의 좌표를 2차원 배열로 저장합니다.
// x, y의 인덱스로 접근하기 위함입니다.
info target[max_int][max_int];

// bfs를 위한 배열 초기화
void init() {
    person_dist = target_dist = max_val;
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            check[i][j] = -1;
        }
    }
}

// 택시의 위치에서 승객까지의 최단거리를 계산합니다.
void person_bfs() {
    
    queue<info> q;
    check[start_x][start_y] = 0;
    q.push({start_x, start_y});
    
    // 만약 시작위치에 승객이 있다면, 거리는 0으로 갱신해줍니다.
    if(a[start_x][start_y] == -1) {
        person_x = start_x;
        person_y = start_y;
        person_dist = check[start_x][start_y];
    }
    
    while(!q.empty()) {
        info cur = q.front();
        q.pop();
        
        int x = cur.x;
        int y = cur.y;
        
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx > n || nx < 1 || ny > n || ny < 1) continue;
            
            if (a[nx][ny] != 1 && check[nx][ny] == -1) {
                check[nx][ny] = check[x][y] + 1;
                
                if(a[nx][ny] == -1) {
                    info next_info = {nx, ny, check[nx][ny]};
                    info person_info = {person_x, person_y, person_dist};
                    
                    // 제일 가까운 승객을 찾아줍니다.
                    if(next_info < person_info) {
                        person_x = nx;
                        person_y = ny;
                        person_dist = check[nx][ny];
                    }
                }
                
                q.push({nx, ny});
            }
        }
    }
}

// 승객의 위치에서 도착지점까지의 최단거리를 계산합니다.
void target_bfs() {
    
    queue<info> q;
    check[person_x][person_y] = 0;
    q.push({person_x, person_y});
    
    while(!q.empty()) {
        info cur = q.front();
        q.pop();
        
        int x = cur.x;
        int y = cur.y;
        
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx > n || nx < 1 || ny > n || ny < 1) continue;
            
            if (a[nx][ny] != 1 && check[nx][ny] == -1) {
                check[nx][ny] = check[x][y] + 1;
                
                // 만약 nx, ny가 도착지점이라면
                // 도착지점까지의 거리를 갱신해줍니다.
                if(nx == target_x && ny == target_y) {
                    target_dist = check[nx][ny];
                }
                
                q.push({nx, ny});
            }
        }
    }
}


int main () {
    // 1. 입력 받습니다.
    scanf("%d %d %d", &n, &m, &oil);
    
    // 1) n*n에 지도의 정보를 입력합니다.
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    
    // 2) 출발지점의 x, y를 입력 저장합니다.
    scanf("%d %d", &start_x, &start_y);
    
    // 3) m 명의 승객 정보를 입력받습니다.
    for(int i=1; i<=m; i++) {
        scanf("%d %d %d %d", &person_x, &person_y, &target_x, &target_y);
        
        // 승객의 위치는 지도에서 -1로 표시합니다.
        a[person_x][person_y] = -1;
        
        // 승객의 도착지점을 저장합니다.
        target[person_x][person_y] = {target_x, target_y};
    }
    
    person_cnt = m;
    
    // 남은 승객의 수 만큼 반복합니다.
    while(person_cnt > 0) {
        
        // bfs를 위한 초기화
        init();
        
        // 1) 택시의 위치에서 가장 가까운 승객을 찾습니다.
        person_bfs();
        
        // 승객 까지 갈 수 없으면 종료합니다.
        if(oil <= person_dist) break;
        
        // 기름을 소모해줍니다.
        oil -= person_dist;
        
        // 승객을 태우면 지도에 표시한 -1을 지워줍니다.
        a[person_x][person_y] = 0;
        
        // 도착 지점의 정보를 갱신합니다.
        info target_info = target[person_x][person_y];
        target_x = target_info.x;
        target_y = target_info.y;
        
        // bfs를 위한 초기화
        init();
        
        // 2) 승객의 위치에서 도착지점까지의 최단 거리를 구합니다.
        target_bfs();
        
        // 도착할 수 없으면 종료합니다.
        if(oil < target_dist) break;
        
        // 소비한 만큼 기름을 채워줍니다.
        oil += target_dist;
        
        // 승객 1명을 줄여줍니다.
        person_cnt--;
        
        // 출발지점을 도착지점의 좌표로 갱신합니다.
        start_x = target_x;
        start_y = target_y;
    }
    
    // 아직 태우지 못한 승객이 있으면 -1록 갱신합니다.
    if(person_cnt > 0) oil = -1;
        
    // 출력
    printf("%d\n", oil);
}

2) java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

    static int max_val = 2147483647;
    static int n, m, oil, a[][], start_x, start_y, person_x, person_y, target_x, target_y, person_dist, target_dist, person_cnt, check[][];
    static Info target[][];
    static int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        oil = Integer.parseInt(st.nextToken());

        a = new int[n+1][n+1];
        target = new Info[n+1][n+1];
        check = new int[n+1][n+1];

        for(int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        start_x = Integer.parseInt(st.nextToken());
        start_y = Integer.parseInt(st.nextToken());

        for(int i=1; i<=m; i++) {
            st = new StringTokenizer(br.readLine());

            person_x = Integer.parseInt(st.nextToken());
            person_y = Integer.parseInt(st.nextToken());
            target_x = Integer.parseInt(st.nextToken());
            target_y = Integer.parseInt(st.nextToken());

            a[person_x][person_y] = -1;

            target[person_x][person_y] = new Info(target_x, target_y);
       }

        person_cnt = m;

        while(person_cnt > 0) {

            init();

            person_bfs();

            if(oil <= person_dist) break;

            oil -= person_dist;

            a[person_x][person_y] = 0;

            Info target_info = target[person_x][person_y];
            target_x = target_info.x;
            target_y = target_info.y;

            init();

            target_bfs();

            if(oil < target_dist) break;

            oil += target_dist;

            person_cnt--;

            start_x = target_x;
            start_y = target_y;
        }

        if(person_cnt > 0) oil = -1;

        System.out.println(oil);
    }

    public static void init() {
        person_dist = target_dist = max_val;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                check[i][j] = -1;
            }
        }
    }

    public static void person_bfs() {
        Queue<Info> q = new LinkedList<>();
        q.add(new Info(start_x, start_y));
        check[start_x][start_y] = 0;

        if(a[start_x][start_y] == -1) {
            person_x = start_x;
            person_y = start_y;
            person_dist = check[start_x][start_y];
        }

        while(!q.isEmpty()) {
            Info cur = q.poll();
            int x = cur.x;
            int y = cur.y;

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

                if(nx > n || nx < 1 || ny > n || ny < 1) continue;

                if(a[nx][ny] != 1 && check[nx][ny] == -1) {
                    check[nx][ny] = check[x][y] + 1;

                    if(a[nx][ny] == -1) {
                        if(check[nx][ny] == person_dist) {
                            if(nx == person_x) {
                                if(ny < person_y) {
                                    person_dist = check[nx][ny];
                                    person_x = nx;
                                    person_y = ny;
                                }
                            }
                            else if(nx < person_x){
                                person_dist = check[nx][ny];
                                person_x = nx;
                                person_y = ny;
                            }
                        }
                        else if(check[nx][ny] < person_dist){
                            person_dist = check[nx][ny];
                            person_x = nx;
                            person_y = ny;
                        }
                    }
                    q.add(new Info(nx, ny));
                }
            }
        }
    }

    public static void target_bfs() {
        Queue<Info> q = new LinkedList<>();
        q.add(new Info(person_x, person_y));
        check[person_x][person_y] = 0;

        while(!q.isEmpty()) {
            Info cur = q.poll();
            int x = cur.x;
            int y = cur.y;

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

                if(nx > n || nx < 1 || ny > n || ny < 1) continue;

                if(a[nx][ny] != 1 && check[nx][ny] == -1) {
                    check[nx][ny] = check[x][y] + 1;

                    if(nx == target_x && ny == target_y) {
                        target_dist = check[nx][ny];
                    }

                    q.add(new Info(nx, ny));
                }
            }
        }
    }

    public static class Info {
        int x, y;

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

3) python3

from collections import deque


def init():
    global person_dist, target_dist, check
    person_dist = target_dist = 2147483647
    check = [[-1 for _ in range(n+1)] for _ in range(n+1)]


def person_bfs():
    global person_x, person_y, person_dist

    q = deque()
    check[start_x][start_y] = 0
    q.append((start_x, start_y))

    if a[start_x][start_y] == -1:
        person_x, person_y, person_dist = start_x, start_y, check[start_x][start_y]

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx > n or nx < 1 or ny > n or ny < 1:
                continue

            if a[nx][ny] != 1 and check[nx][ny] == -1:
                check[nx][ny] = check[x][y] + 1

                if a[nx][ny] == -1:
                    if person_dist == check[nx][ny]:
                        if nx == person_x:
                            if ny < person_y:
                                person_x, person_y, person_dist = nx, ny, check[nx][ny]
                        elif nx < person_x:
                            person_x, person_y, person_dist = nx, ny, check[nx][ny]

                    elif check[nx][ny] < person_dist:
                        person_x, person_y, person_dist = nx, ny, check[nx][ny]

                q.append((nx, ny))


def target_bfs():
    global target_dist

    q = deque()
    check[person_x][person_y] = 0
    q.append((person_x, person_y))

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx > n or nx < 1 or ny > n or ny < 1:
                continue

            if a[nx][ny] != 1 and check[nx][ny] == -1:
                check[nx][ny] = check[x][y] + 1

                if nx == target_x and ny == target_y:
                    target_dist = check[nx][ny]

                q.append((nx, ny))


n, m, oil = map(int, input().split())
a = []
a.append([0 for _ in range(n+1)])
check = [[-1 for _ in range(n+1)] for _ in range(n+1)]
target = [[(0, 0) for _ in range(n+1)] for _ in range(n+1)]
person_x = person_y = target_x = target_y = 0
person_dist = target_dist = 0
dx = 0, 0, 1, -1
dy = -1, 1, 0, 0

for i in range(n):
    arr = [0] + list(map(int, input().split()))
    a.append(arr)

start_x, start_y = map(int, input().split())

for _ in range(m):
    person_x, person_y, target_x, target_y = map(int, input().split())
    a[person_x][person_y] = -1

    target[person_x][person_y] = (target_x, target_y)

person_cnt = m

while person_cnt > 0:

    init()

    person_bfs()

    if oil <= person_dist:
        break

    oil -= person_dist

    a[person_x][person_y] = 0

    target_x, target_y = target[person_x][person_y]

    init()

    target_bfs()

    if oil < target_dist:
        break

    oil += target_dist

    person_cnt -= 1

    start_x, start_y = target_x, target_y

if person_cnt > 0:
    oil = -1

print(oil)