19238 - 스타트 택시

 

---

 

문제

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

19238번: 스타트 택시

 

풀이

은근 까다로운 문제이다. 

 

일반적인 bfs에 조건을 잘 걸어서 문제를 풀어야한다.

 

우선 나는 입력값을 조금 조정했다. 1부터 N까지가 아니라, 0부터 N-1로 설정했고, 벽은 1이 아니라 -1로, 빈칸은 0이 아니라 -9로 설정했다. 이유는 입력받은 2차원 배열에 손님들의 위치를 저장해두기 위해서이다. 해당 위치는 bfs를 돌면서 판단할 때 사용한다.

 

또한 나는 손님의 번호를 기준으로 기다리는 위치에서 목적지의 거리와, 목적지의 좌표를 저장해두었다. 이는 추후에 계산을 용이하게 하기 위함이다.

 

이렇게 까지 세팅한다음에 문제를 풀었다.

 

우선 시작 위치에서 bfs를 수행한다. 이 때 가장 가까운 거리에 있는 손님의 위치를 찾아야한다. 단, 거리가 같을때는 행이 작은 순으로, 행마저 같다면 열이 작은 위치의 손님을 선택한다. 이를 고르기 위해서 나는 최소거리에서 손님을 찾았을때 우선적으로 후보리스트에 넣어주었다. 이후에는 행과 열을 기준으로 오름차순해서 정렬했다. 그렇게 되면, 거리는 다 똑같으니까 행이 작은순으로, 행이 같다면 열이 작은순으로 정렬이 될 것이다. 

(bfs수행중 손님의 위치가 아닌 경우에는 bfs를 계속 수행하도록 값을 갱신해주어야 한다. 당연하지만..)

 

그렇게 선택된 손님의 위치의 거리와, 미리 구해둔 손님의 위치~도착지의 위치 값을 더해서 현재 지닌 기름으로 갈 수 있는지 판단한다. 만약 못간다면 정답을 -1로 출력해주면 되고, 가능하다면 기름값을 계산하고 시작 위치를 선택한 손님의 도착지로 설정해주면 된다.  (미리 저장해둔 손님번호로 도착지를 저장해둔 배열을 사용하면 된다.)

 

전체적인 흐름은 이러하고 예외처리를 하나 해줘야 하는데, 택시의 시작 위치와 손님의 위치가 같을때이다. bfs는 현재 좌표를 기준으로 상하좌우를 탐색하기에 처음좌표에 손님이 있다면 이때만 예외처리를 해서 리턴해주면 된다.

 

 

코드

import sys
from sys import stdin
from collections import deque

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

def bfs(s):
    global fuel, n, board, dx, dy, endPoint
    candid = []
    dis = [[-1] * n for _ in range(n)]
    dis[s[0]][s[1]] = 0
    q = deque()
    q.append(s)

    # 택시가 있는곳이 시작 위치인 경우
    if board[s[0]][s[1]] != -9:
        if fuel - distance[board[s[0]][s[1]]] >= 0:
            num = board[s[0]][s[1]]
            fuel += distance[num]
            board[s[0]][s[1]] = -9
            return endPoint[num]
        return -1

    # 그 외의 경우
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != -1 and dis[nx][ny] == -1:
                if board[nx][ny] != -9:
                    # candid = [택시로부터 이용자의 거리, 택시 이용자의 행, 택시 이용자의 열, 택시이용자 번호]
                    if len(candid) == 0: candid.append([dis[x][y]+1, nx, ny, board[nx][ny]])
                    elif candid[0][0] == dis[x][y]+1 : candid.append([dis[x][y]+1, nx, ny, board[nx][ny]])
                    else: break
                dis[nx][ny] = dis[x][y] + 1
                q.append((nx, ny))

    if len(candid) == 0 : return -1

    ans = sorted(candid, key = lambda x : (x[1], x[2]))[0]

    if fuel - (ans[0] + distance[ans[-1]]) >= 0:
        fuel -= (ans[0] + distance[ans[-1]])
        fuel += distance[ans[-1]]*2
        board[ans[1]][ans[2]] = -9
        return endPoint[ans[-1]]
    return -1

# 택시 이용자의 위치에서 도착지까지의 거리를 구한다.
def getDistance(s, e):
    dis = [[-1] * n for _ in range(n)]
    dis[s[0]][s[1]] = 0
    q = deque()
    q.append(s)

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

            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != -1 and dis[nx][ny] == -1:
                if nx == e[0] and ny == e[1]:
                    return dis[x][y] + 1
                else:
                    dis[nx][ny] = dis[x][y] + 1
                    q.append((nx, ny))
    return sys.maxsize

"""
**********
   MAIN
**********
"""

n, m, fuel = map(int, input().split())
board = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
distance = []
endPoint = []
# 벽은 -1로 세팅, 빈칸은 -9로 세팅
for i in range(n):
    for j in range(n):
        board[i][j] = -1 if board[i][j] == 1 else -9

start = list(map(int, input().split()))
start[0] -= 1
start[1] -= 1
cnt = 0

for _ in range(m):
    temp = list(map(int, stdin.readline().rstrip().split()))
    for i in range(len(temp)) : temp[i] -= 1
    board[temp[0]][temp[1]] = cnt
    distance.append(getDistance((temp[0], temp[1]), (temp[2], temp[3])))
    endPoint.append([temp[2], temp[3]])
    cnt += 1

possible = True
for _ in range(m):
    res = bfs(start)
    if res == -1:
        possible = False
        break
    else:
        start = res

print(fuel) if possible else print(-1)

 

후기

 

네부캠 챌린지를 끝내고 약 한달만에 문제를 풀었다.

 

문제가 단순한 거 같으면서도 예외를 캐치하지 못하면 예외처리 지옥에 빠지기 때문에 꽤나 시간이 걸렸다.

 

처음 맞았을때 코드가 너무 지저분해서 개선을 좀 해서 다시 풀었다. 확실히 깔끔해져서 좋으나 처음부터 이렇게 작성할 수 있도록 노력해야할 거 같다.