백준 19238번 문제 - BFS & 구현

 

이번 글은 삼성 코테 기출 문제인 19238번 문제를 복기하면서 쓰는 글이다.

https://www.acmicpc.net/problem/19238

 

 

해당 문제는 문제설명에서도 나와있듯이, 택시가 승객이 위치한 곳으로 이동해야하며 이때 택시의 위치에서 가장 가까운 위치에 있는, 즉 최단경로에 있는 승객을 태우러 가기 때문에 BFS 알고리즘을 떠올려야 했다. + 조건을 잘 따져가면서 풀어야 하는게 중요했다.

 

해당 문제는 눈높이 개발에서 진행하는 코딩테스트 챌린지를 진행하면서 푼 문제인데, 여기서 힌트를 주신게 메모리 초과가 나지않게 점검해보라고 하셨던 거였다! 그래서 처음에 딱 생각이 났던게, 택시와 승객의 최단 경로 길이를 구해야하는데 이걸 승객마다 BFS를 돌리기에는 시간초과가 뜰 것 같다는 생각이 들었다. 그래서 처음에 택시가 한 턴을 돌때, 즉 택시가 승객이 있는 위치로 이동하기 위해 모든 승객의 최단 경로를 한 번의 BFS를 통해 구해야겠다고 생각했다.

 

*(코딩 테스트 챌린지 굉장히 추천합니다.. 매일매일 코테를 의무적으로 풀기 좋고, 문제도 좋은 문제로 선별해주시고 풀이집도 나중에 제공해주셔서 아주 좋다는..!) 

 

 

✅ 문제 해결 과정

1. 현재 위치에서 가장 가까운 승객을 찾는다.
   • BFS를 사용하여 최단 거리를 계산하고, 가장 가까운 승객을 선택한다.
   • 거리가 같은 승객이 여러 명일 경우, 행 번호가 작은 승객 → 열 번호가 작은 승객 순으로 정렬한다.
2. 승객을 태우고 목적지까지 이동한다.
   • 승객을 태울 때 연료를 소모하며, 이동 도중 연료가 0이 되면 실패(-1출력).
   • 목적지까지 도착하면 사용한 연료의 두 배를 충전한다.
3. 위 과정을 M번 반복하여 모든 승객을 목적지까지 이동시킨다.
   • 이동 중 연료가 부족하거나, 목적지까지 갈 수 없는 경우 -1 출력.
   • 모든 승객을 성공적으로 이동시킨다면 남은 연료의 양을 출력.

 

✅ 코드 설계하기

1. 승객과 맵 정보를 입력받는다.
   • 지도 정보(maps)를 입력받는다.
   • 택시의 초기 위치를 저장한다.
   • 승객 정보를 리스트(customers)에 저장한다.
2. BFS를 이용하여 특정 위치에서 모든 위치까지의 최단 거리 계산 함수 (getDistance())를 구현한다.
   • getDistance(a, b): (a, b) 위치에서 모든 좌표까지의 최단 거리를 계산하여 distance_map을 반환한다.
3. 가장 가까운 승객을 찾는 과정
   • getDistance()를 이용하여 모든 승객까지의 최단 거리를 구한다.
   • 승객을 (최단 거리, 행 번호, 열 번호) 기준으로 오름차순 정렬하여 가장 우선순위 높은 승객을 선택한다.
4. 승객을 목적지까지 이동시키는 과정 (moveToDestination())
   • 승객을 태우러 가는 데 연료를 소모한다.
   • 승객을 목적지까지 이동시키는 데 연료를 소모한다.
   • 도착하면 사용한 연료의 두 배를 충전한다.
5. 모든 승객을 이동시킬 때까지 위 과정을 M번 반복한다.
   • 연료가 부족하거나 이동할 수 없는 경우 -1을 출력하고 종료한다.
   • 모든 승객을 이동시킨 경우 남은 연료를 출력한다.

 

여기서 내가 놓쳤던 포인트 두 가지가 있었다.

 

1. 승객이 택시가 데릴러 갈 수 없는 곳에 위치 할 수도 있다.

벽에 가로 막혀서 택시가 승객이 있는 곳 또는 승객이 원하는 도착지로 갈 수 없다는 사실을 찾아내는게 중요했다.

그래서 distance_map을 모두 -1로 초기화를 하고, BFS를 돈 후에 승객이 있는 곳의 최단경로 길이가 -1이거나, 승객이 원하는 도착지의 최단경로 길이가 -1이라면 -1을 출력하고 종료한다.

distance_map = [[-1 for _ in range(n)] for _ in range(n)]

 

 

2. 해당 조건을 어떻게 처리할 것인가?

아래 조건이 주어졌는데, 이걸 어떻게 코드에 적용할 지가 어려웠다.. 그래서 이건 구글링의 도움을 받았다. lamda로 정렬하는 건 익숙해져야겠다,,

customers.sort(key=lambda c: (distance_map[c[0]][c[1]], c[0], c[1]))

1. 최단경로의 길이가 가장 짧은 승객 방문
   1. 같다면, 행의 번호가 가장 작은 승객 방문
   2. 같다면, 열의 번호가 가장 작은 승객 방문

 

✅ 정답코드

import sys
from collections import deque

input = sys.stdin.readline

n, m, fuel = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]

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

customers = []
for _ in range(m):
    x, y, to_x, to_y = map(int, input().split())
    customers.append([x-1, y-1, to_x-1, to_y-1])

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def getDistance(a, b):
    distance_map = [[-1 for _ in range(n)] for _ in range(n)]
    visited = [[False for _ in range(n)] for _ in range(n)]
    q = deque([(a, b, 0)])
    visited[a][b] = True
    distance_map[a][b] = 0

    while q:
        x, y, distance = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if not visited[nx][ny] and maps[nx][ny] == 0:
                    visited[nx][ny] = True
                    distance_map[nx][ny] = distance + 1
                    q.append((nx, ny, distance + 1))
    return distance_map

def moveToDestination(d, customer_x, customer_y, to_go_x, to_go_y):
    global fuel, start_x, start_y

    fuel -= d
    if fuel < 0:
        return -1

    distance_map = getDistance(customer_x, customer_y)
    distance = distance_map[to_go_x][to_go_y]

    #도착지까지 갈 수가 없는 경우(경로가 없음)
    if distance == -1:
        return -1

    fuel -= distance
    if fuel < 0:
        return -1

    fuel += distance * 2
    start_x, start_y = to_go_x, to_go_y
    return True

for _ in range(m):
    distance_map = getDistance(start_x, start_y)

    customers.sort(key=lambda c: (distance_map[c[0]][c[1]], c[0], c[1]))

    x, y, to_x, to_y = customers.pop(0)

    if distance_map[x][y] == -1:
        fuel = -1
        break

    result = moveToDestination(distance_map[x][y], x, y, to_x, to_y)
    if result != True:
        fuel = -1
        break

print(fuel)