[문제풀이-백준] 19238. 스타트 택시

Sjin·2021년 4월 29일
백준
0

삼성 기출

목록 보기
12/20

풀이

BFS

시간 복잡도

O(n^2)

처음 생각했던 아이디어

  • 주어진 맵 정보에 손님 번호를 추가로 표시 해줌
  • 손님의 위치와 도착지 정보를 각각 리스트로 만듬
  • 손님 번호 리스트를 만듬

=> 여러 명의 손님이 같은 도착지를 공유할 때, 정보가 덮어씌워지므로 에러

개선 방안

  • 주어진 맵 정보는 건드리지 않음
  • 손님의 출발지 정보와 도착지 정보를 쌍으로 갖는 딕셔너리 이용

구현 방법

  • 태울 수 있는 손님 찾기 [BFS] - 20 20 2

    모든 손님의 위치를 찾은 후, min(key)를 이용하여 우선순위가 높은 손님 한명 뽑기

  • 손님을 태우고 목적지로 출발 [BFS] - 20 * 20

    • 실패하면 -1 리턴

  • 리턴 값 확인

    • 목적지에 도착할 수 있으면 연료 업데이트

  • 모든 손님을 태웠는지 확인 20*20

    • 아직 태울 수 있는 손님은 c_visited에 True로 표시되있음

예외 처리

  • 손님을 태웠으나 도착지로 못가는 경우
  • 태울 손님이 없을 경우
  • 도착지에 새로운 손님이 있을 경우
  • 도착지가 같은 손님이 여러명일 때

팁

  • 주어진 맵 정보는 건드리지 말 것
  • deepcopy는 하지 말 것
  • 디버깅시엔 툴을 이용하지 말고, print를 찍어봐야한다. 그 다음, 빠르게 추가 테스트케이스를 만들어서 확인해야한다.

도움되는 테스트 케이스

https://www.acmicpc.net/board/view/58112

# 6 5 19
# 1 0 0 0 1 0
# 1 0 1 0 1 0
# 1 0 1 0 1 0
# 1 0 1 0 1 0
# 1 0 1 0 1 0
# 0 0 1 0 0 0
# 1 3
# 6 1 1 6
# 1 6 6 2
# 5 2 2 4
# 6 5 6 6
# 4 6 1 2

# ans = 59
20 400 500000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17 14
1 1 5 5
1 2 5 5
1 3 5 5
1 4 5 5
1 5 5 5
1 6 5 5
1 7 5 5
1 8 5 5
1 9 5 5
1 10 5 5
1 11 5 5
1 12 5 5
1 13 5 5
1 14 5 5
1 15 5 5
1 16 5 5
1 17 5 5
1 18 5 5
1 19 5 5
1 20 5 5
2 1 5 5
2 2 5 5
2 3 5 5
2 4 5 5
2 5 5 5
2 6 5 5
2 7 5 5
2 8 5 5
2 9 5 5
2 10 5 5
2 11 5 5
2 12 5 5
2 13 5 5
2 14 5 5
2 15 5 5
2 16 5 5
2 17 5 5
2 18 5 5
2 19 5 5
2 20 5 5
3 1 5 5
3 2 5 5
3 3 5 5
3 4 5 5
3 5 5 5
3 6 5 5
3 7 5 5
3 8 5 5
3 9 5 5
3 10 5 5
3 11 5 5
3 12 5 5
3 13 5 5
3 14 5 5
3 15 5 5
3 16 5 5
3 17 5 5
3 18 5 5
3 19 5 5
3 20 5 5
4 1 5 5
4 2 5 5
4 3 5 5
4 4 5 5
4 5 5 5
4 6 5 5
4 7 5 5
4 8 5 5
4 9 5 5
4 10 5 5
4 11 5 5
4 12 5 5
4 13 5 5
4 14 5 5
4 15 5 5
4 16 5 5
4 17 5 5
4 18 5 5
4 19 5 5
4 20 5 5
5 1 5 5
5 2 5 5
5 3 5 5
5 4 5 5
5 5 5 6
5 6 5 5
5 7 5 5
5 8 5 5
5 9 5 5
5 10 5 5
5 11 5 5
5 12 5 5
5 13 5 5
5 14 5 5
5 15 5 5
5 16 5 5
5 17 5 5
5 18 5 5
5 19 5 5
5 20 5 5
6 1 5 5
6 2 5 5
6 3 5 5
6 4 5 5
6 5 5 5
6 6 5 5
6 7 5 5
6 8 5 5
6 9 5 5
6 10 5 5
6 11 5 5
6 12 5 5
6 13 5 5
6 14 5 5
6 15 5 5
6 16 5 5
6 17 5 5
6 18 5 5
6 19 5 5
6 20 5 5
7 1 5 5
7 2 5 5
7 3 5 5
7 4 5 5
7 5 5 5
7 6 5 5
7 7 5 5
7 8 5 5
7 9 5 5
7 10 5 5
7 11 5 5
7 12 5 5
7 13 5 5
7 14 5 5
7 15 5 5
7 16 5 5
7 17 5 5
7 18 5 5
7 19 5 5
7 20 5 5
8 1 5 5
8 2 5 5
8 3 5 5
8 4 5 5
8 5 5 5
8 6 5 5
8 7 5 5
8 8 5 5
8 9 5 5
8 10 5 5
8 11 5 5
8 12 5 5
8 13 5 5
8 14 5 5
8 15 5 5
8 16 5 5
8 17 5 5
8 18 5 5
8 19 5 5
8 20 5 5
9 1 5 5
9 2 5 5
9 3 5 5
9 4 5 5
9 5 5 5
9 6 5 5
9 7 5 5
9 8 5 5
9 9 5 5
9 10 5 5
9 11 5 5
9 12 5 5
9 13 5 5
9 14 5 5
9 15 5 5
9 16 5 5
9 17 5 5
9 18 5 5
9 19 5 5
9 20 5 5
10 1 5 5
10 2 5 5
10 3 5 5
10 4 5 5
10 5 5 5
10 6 5 5
10 7 5 5
10 8 5 5
10 9 5 5
10 10 5 5
10 11 5 5
10 12 5 5
10 13 5 5
10 14 5 5
10 15 5 5
10 16 5 5
10 17 5 5
10 18 5 5
10 19 5 5
10 20 5 5
11 1 5 5
11 2 5 5
11 3 5 5
11 4 5 5
11 5 5 5
11 6 5 5
11 7 5 5
11 8 5 5
11 9 5 5
11 10 5 5
11 11 5 5
11 12 5 5
11 13 5 5
11 14 5 5
11 15 5 5
11 16 5 5
11 17 5 5
11 18 5 5
11 19 5 5
11 20 5 5
12 1 5 5
12 2 5 5
12 3 5 5
12 4 5 5
12 5 5 5
12 6 5 5
12 7 5 5
12 8 5 5
12 9 5 5
12 10 5 5
12 11 5 5
12 12 5 5
12 13 5 5
12 14 5 5
12 15 5 5
12 16 5 5
12 17 5 5
12 18 5 5
12 19 5 5
12 20 5 5
13 1 5 5
13 2 5 5
13 3 5 5
13 4 5 5
13 5 5 5
13 6 5 5
13 7 5 5
13 8 5 5
13 9 5 5
13 10 5 5
13 11 5 5
13 12 5 5
13 13 5 5
13 14 5 5
13 15 5 5
13 16 5 5
13 17 5 5
13 18 5 5
13 19 5 5
13 20 5 5
14 1 5 5
14 2 5 5
14 3 5 5
14 4 5 5
14 5 5 5
14 6 5 5
14 7 5 5
14 8 5 5
14 9 5 5
14 10 5 5
14 11 5 5
14 12 5 5
14 13 5 5
14 14 5 5
14 15 5 5
14 16 5 5
14 17 5 5
14 18 5 5
14 19 5 5
14 20 5 5
15 1 5 5
15 2 5 5
15 3 5 5
15 4 5 5
15 5 5 5
15 6 5 5
15 7 5 5
15 8 5 5
15 9 5 5
15 10 5 5
15 11 5 5
15 12 5 5
15 13 5 5
15 14 5 5
15 15 5 5
15 16 5 5
15 17 5 5
15 18 5 5
15 19 5 5
15 20 5 5
16 1 5 5
16 2 5 5
16 3 5 5
16 4 5 5
16 5 5 5
16 6 5 5
16 7 5 5
16 8 5 5
16 9 5 5
16 10 5 5
16 11 5 5
16 12 5 5
16 13 5 5
16 14 5 5
16 15 5 5
16 16 5 5
16 17 5 5
16 18 5 5
16 19 5 5
16 20 5 5
17 1 5 5
17 2 5 5
17 3 5 5
17 4 5 5
17 5 5 5
17 6 5 5
17 7 5 5
17 8 5 5
17 9 5 5
17 10 5 5
17 11 5 5
17 12 5 5
17 13 5 5
17 14 5 5
17 15 5 5
17 16 5 5
17 17 5 5
17 18 5 5
17 19 5 5
17 20 5 5
18 1 5 5
18 2 5 5
18 3 5 5
18 4 5 5
18 5 5 5
18 6 5 5
18 7 5 5
18 8 5 5
18 9 5 5
18 10 5 5
18 11 5 5
18 12 5 5
18 13 5 5
18 14 5 5
18 15 5 5
18 16 5 5
18 17 5 5
18 18 5 5
18 19 5 5
18 20 5 5
19 1 5 5
19 2 5 5
19 3 5 5
19 4 5 5
19 5 5 5
19 6 5 5
19 7 5 5
19 8 5 5
19 9 5 5
19 10 5 5
19 11 5 5
19 12 5 5
19 13 5 5
19 14 5 5
19 15 5 5
19 16 5 5
19 17 5 5
19 18 5 5
19 19 5 5
19 20 5 5
20 1 5 5
20 2 5 5
20 3 5 5
20 4 5 5
20 5 5 5
20 6 5 5
20 7 5 5
20 8 5 5
20 9 5 5
20 10 5 5
20 11 5 5
20 12 5 5
20 13 5 5
20 14 5 5
20 15 5 5
20 16 5 5
20 17 5 5
20 18 5 5
20 19 5 5
20 20 5 5

ans = 500023

코드

기존
from collections import deque

def start_bfs(y,x,d):
    deq = deque()
    if start[y][x] > 1 and not customer[start[y][x]]:
        Cs.append([y,x,d,start[y][x]])
        return
    deq.append([y,x,d])
    visited[y][x] = True

    while deq:
        y,x,d = deq.popleft()
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and start[ny][nx] > 1 and not customer[start[ny][nx]]:
                Cs.append([ny , nx, d + 1, start[ny][nx]])
                deq.append([ny, nx, d + 1])
                visited[ny][nx] = True
            elif 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and start[ny][nx] != 1:
                deq.append([ny, nx, d + 1])
                visited[ny][nx] = True


def dest_bfs(lst):
    y,x,fuel,idx = lst
    if end[y][x] == idx and fuel <= tank:
        dest.append(y)
        dest.append(x)
        return 0
    deq=deque()
    deq.append([y,x,0])
    visited[y][x] = True

    while deq:
        y,x,d = deq.popleft()
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and end[ny][nx] == idx and fuel+d+1 <= tank:
                dest.append(ny)
                dest.append(nx)
                return d+1
            elif 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and end[ny][nx] != 1 and fuel+d+1 <= tank:
                deq.append([ny, nx, d + 1])
                visited[ny][nx] = True
    return -1

direct = [(-1,0),(0,1),(1,0),(0,-1)]
N,M,tank = map(int,input().split())
start = [list(map(int,input().split())) for _ in range(N)]
end = [[0]*N for _ in range(N)]
sy,sx = map(int,input().split())
sy,sx = sy-1,sx-1
adj = {i:[] for i in range(2,M+2)}
customer = [False]*(M+2)
for i in range(2,M+2):
    t = list(map(int,input().split()))
    ts,te = t[:2],t[2:]
    ts[0], ts[1] = ts[0] - 1, ts[1] - 1
    te[0], te[1] = te[0] - 1, te[1] - 1
    adj[i].append(ts)
    adj[i].append(te)
    start[ts[0]][ts[1]] = i
    end[te[0]][te[1]] = i
for i in range(N):
    for j in range(N):
        if start[i][j] == 1:
            end[i][j] = 1
isEnd = False
while not isEnd:
    isEnd = True
    Cs = []
    visited = [[False] * N for _ in range(N)]
    start_bfs(sy,sx,0)

    # 가까운 후보 추려내기
    if not Cs:
        fl = -1
        break
    c = min(Cs, key=lambda x: (x[2],x[0],x[1]))

    # 목적지 찾기
    dest = []
    visited = [[False]*N for _ in range(N)]
    fl = dest_bfs(c)
    if fl == -1:
        isEnd = True
        break
    else:
        sy,sx = dest
        tank = tank - c[2] - fl + fl * 2
        customer[c[3]] = True

    for num in range(2,M+2):
        if not customer[num]:
            isEnd = False

if fl == -1:
    print(-1)
else:
    print(tank)
개선
from _collections import deque

def find_customer(y,x,d):
    if customers.get((y,x)) is not None and c_visited[y][x]:
        Cs.append([y,x,d])
        return
    deq = deque()
    deq.append([y,x,d])
    visited[y][x] = True

    while deq:
        y,x,d = deq.popleft()
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and not visited[ny][nx] and c_visited[ny][nx]:
                Cs.append([ny,nx,d+1])
                deq.append([ny,nx,d+1])
                visited[ny][nx] = True
            elif 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and not visited[ny][nx]:
                deq.append([ny, nx, d + 1])
                visited[ny][nx] = True


def move(lst):
    y,x,fuel = lst
    ey,ex = customers[(y,x)]
    if (y,x) == (ey,ex):
        dest.append(y)
        dest.append(x)
        return 0
    deq = deque()
    deq.append([y,x,0])
    visited[y][x] = True

    while deq:
        y,x,d = deq.popleft()
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and not visited[ny][nx] and (ny,nx) == (ey,ex) and fuel+d+1 <= tank:
                dest.append(ny)
                dest.append(nx)
                return d+1
            elif 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and not visited[ny][nx] and fuel+d+1 <= tank:
                deq.append([ny,nx,d+1])
                visited[ny][nx] = True

    return -1

def check():
    cnt = 0
    for i in range(N):
        for j in range(N):
            if c_visited[i][j]:
                cnt += 1
    if cnt > 0: # 아직 남아있는 손님이 있다면
        return False
    else:
        return True


answer = -1
direct = [(-1,0),(0,1),(1,0),(0,-1)]
N,M,tank = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(N)]
sy,sx = map(int,input().split())
sy,sx = sy-1,sx-1
c_visited = [[False]*N for _ in range(N)] # 손님이 있으면 True
customers = {}
for i in range(M):
    t = list(map(int,input().split()))
    for j in range(4):
        t[j] -= 1
    ts, te = t[:2], t[2:]
    customers[(ts[0],ts[1])] = (te[0],te[1])
    c_visited[ts[0]][ts[1]] = True

isEnd = False
while not isEnd:
    isEnd = True
    Cs = []
    visited = [[False]*N for _ in range(N)]

    find_customer(sy,sx,0)
    # 손님 후보 뽑기
    if not Cs:
        answer = -1
        break
    c = min(Cs, key=lambda x:(x[2],x[0],x[1]))
    # 손님 태우고 출발
    dest = []
    visited = [[False] * N for _ in range(N)]
    fl = move(c)
    if fl == -1:
        answer = -1
        break
    else:
        tank = tank - c[2] + fl
        sy,sx = dest
        c_visited[c[0]][c[1]] = False

    if not check():
        isEnd = False
    else:
        answer = tank

print(answer)
profile
Sjin
웹뷰 개발에 관심 많은 Front-end 개발자입니다.
이전 포스트

[문제풀이-백준] 21608. 상어초등학교

다음 포스트

[문제풀이-백준] 19237. 어른 상어

0개의 댓글

관련 채용 정보