Easy is Perfect

[백준] 19238번 스타트 택시 _ 문제 풀이

  • melonicedlatte
  • Apr 21, 2021


1. 문제

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

2. 풀이

삼성 SW 역량테스트 문제입니다.

최소 거리에 있는 고객을 찾고 목적지 까지의 비용을 찾기 위하여 BFS 를 이용하여 가능한 경우 중에서 답을 선택합니다. 조건 중에 정답을 찾고 탈출하지 않는 경우의 case 를 처리하지 못하여 계속해서 오답이 났었습니다. 모든 경우에서 탈출할 수 있게 꼼꼼히 살펴야 될 것 같습니다.

9967han님이 올려주신 반례글(https://www.acmicpc.net/board/view/52841)을 넣고 겨우 답을 찾을 수 있었습니다. 감사드립니다.

6 4 15
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5
1 6 5 4

자세한 구현 방법은 코드를 참조해주세요.

  • 벽이 있는 칸의 값을 1에서 -1로 바꿔준다
  • 승객이 있는 위치에 번호를 매기고, 승객의 수만큼 반복해서 이동한다.
  • 이동이 완료되면 승객의 칸을 0으로 바꿔준다
from collections import deque
# 위 오른쪽 아래 왼쪽
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
N, M, fuel = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]
WALL = -987654
maps = [[WALL if maps[r][c] == 1 else maps[r][c] for c in range(N)] for r in range(N)]
driver = list(map(int, input().split()))
driver = [driver[0]-1, driver[1]-1]
client = [[] for _ in range(M + 1)]
client_dest = [[] for _ in range(M + 1)]
deliver_complete = 0
for m_i in range(1, M+1):
    r, c, dest_r, dest_c = list(map(int, input().split()))
    maps[r-1][c-1] = m_i
    client[m_i].extend([r-1, c-1])
    client_dest[m_i].extend([dest_r-1, dest_c-1])


# 최소 거리에 있는 고객 찾기 - BFS 사용함
def find_next_client():
    need_distance = 0
    is_visited = [[False for __ in range(N)] for _ in range(N)]
    # 만약 같은 위치에 있으면 바로 return
    if maps[driver[0]][driver[1]] > 0:
        return need_distance, maps[driver[0]][driver[1]]
    que = deque([[driver[0], driver[1]]])
    while len(que):
        need_distance += 1
        this_round_clients = []
        round_num = len(que)
        for r_i in range(round_num):
            now_cord = que.popleft()
            if is_visited[now_cord[0]][now_cord[1]]:
                continue
            is_visited[now_cord[0]][now_cord[1]] = True

            for i in range(4):
                new_r = now_cord[0] + dr[i]
                new_c = now_cord[1] + dc[i]
                # out of index or wall
                if new_r < 0 or new_r >= N or new_c < 0 or new_c >= N or maps[new_r][new_c] == WALL or is_visited[new_r][new_c]:
                    continue
                # 가능한 손님이라면
                if maps[new_r][new_c] > 0:
                    this_round_clients.append([new_r, new_c])
                que.append([new_r, new_c])

        if len(this_round_clients) >= 1:
            picked_client = sorted(this_round_clients, key=lambda x: (x[0], x[1]))[0]
            client_n = maps[picked_client[0]][picked_client[1]]
            # maps[picked_client[0]][picked_client[1]] = 0
            return need_distance, client_n

    return -1, -1


# 해당 목적지까지 가는데 걸리는 비용 산정해보기
def get_distance(start, end):
    need_distance = 0
    is_visited = [[False for __ in range(N)] for _ in range(N)]
    if start == end:
        return need_distance
    que = deque([[start[0], start[1]]])
    while len(que):
        need_distance += 1
        for r_i in range(len(que)):
            now_cord = que.popleft()
            if is_visited[now_cord[0]][now_cord[1]]:
                continue
            is_visited[now_cord[0]][now_cord[1]] = True

            for i in range(4):
                new_r = now_cord[0] + dr[i]
                new_c = now_cord[1] + dc[i]
                # out of index or wall
                if new_r < 0 or new_r >= N or new_c < 0 or new_c >= N or maps[new_r][new_c] == WALL or is_visited[new_r][new_c]:
                    continue
                if [new_r, new_c] == end:
                    return need_distance
                else:
                    que.append([new_r, new_c])
    return -1


# 다음 목적지까지 이동
while True:
    # 최소 거리에 있는 고객 찾기
    client_need, client_num = find_next_client()
    maps[client[client_num][0]][client[client_num][1]] = 0
    if client_need == -1 or fuel - client_need < 0:
        print(-1)
        break
    fuel -= client_need
    s_to_e = get_distance(client[client_num], client_dest[client_num])
    if s_to_e == -1 or fuel - s_to_e < 0:
        print(-1)
        break
    else:
        fuel += s_to_e
        deliver_complete += 1
        driver = [client_dest[client_num][0], client_dest[client_num][1]]
        if deliver_complete == M:
            print(fuel)
            break



Search