문제
출처: https://www.acmicpc.net/problem/19238
나의 접근법
그래프에 남은 연료를 넣기 위해 벽을 -1로 변경
손님들의 위치 정보와 도착정보를 따로 저장
BFS()
1. 먼저 현재 위치에 손님이 있는지 확인
2. BFS로 거리 1차이 나는 거리 확인
-> q에 넣기
3. 같은 거리에 또 다른 손님이 있는지, 첫 손님은 찾았는지, 거리가 같은지
-> custList에 추가
4. 현재 g에 넣는 연료 (남은 연료)가 첫 손님을 찾았을 때 남은 연료보다 작은지
-> 작다면 거리가 같은 손님은 다 찾은 것 -> 정렬 후 행이 낮고 열이 낮은 손님부터 목적지 찾기
5. 가까운 손님을 첫손님을 찾은 경우 -> custList에 추가
5-1 만약 그 첫 손님이 마지막 칸에 있는 경우 -> 바로 목적지 찾기
findDest()
1. 연료가 바닥난 경우 -> 종료
2. 도착지를 찾은 경우 -> 이동할때 연료 2배 추가하여 연료 반환
3. 방문 가능한 칸 탐색
4. 연료가 다 떨어진 칸의 주위가 벽으로 둘러 싸인 경우 -> 종료
주의 사항
1. 가장 가까운 손님을 찾는데 ↑ ← → ↓ 순서로 BFS를 탐색하면 안됩니다.
같은 거리에 두 손님이 있는 경우 행이 낮은 순서, 그것도 같다면 열이 낮은 순서로 찾으라고 조건에 나와있습니다.
=> 저의 경우, BFS로 어느 한 손님을 찾으면 같은 거리의 또 다른 손님 있는지 확인하고 있으면 리스트에 넣어 sort하여 행이 낮은 손님을 우선 태웠습니다.
2. 손님이 가장 먼 칸에 존재하는 경우
마지막 칸에 도착할 때 큐에 손님이 없어서 BFS를 마무리하는 경우가 있는데 이렇게 작동되면 안됩니다.
=> 더 이상 방문할 큐가 비었는데 손님은 있는 경우 바로 목적지를 탐색할 수 있게 만들었습니다.
위와 같은 특이사항의 경우 아래의 반례를 통해 커버가 가능합니다.
반례
10 1 5000
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
5 5
10 10 5 5
정답 5000
3. 손님이 여러 명인 경우 시작지점은 다르지만 각 손님의 도착 지점은 같을 수 있습니다.
저는 startLink와 endLink라는 link를 도입해 여러 손님이 한 개의 도착지점을 갈 수 있게 만들었습니다.
즉 맵에 바로 손님의 도착지점을 저장하는 것이 아니라 손님 별로 i 라는 인덱스를 저장시켜 택시가 손님을 찾았을 때 인덱스 값으로 목적지를 찾아갔습니다.
4. 택시의 시작 지점에 바로 손님이 있는 경우입니다.
저는 BFS를 시작하자마자 현재 위치를 방문으로 처리하고 dx, dy를 돌리는 것이 아니라 시작과 동시에 손님이 있는지 확인 하였습니다.
아래의 반례를 통해 확인할 수 있습니다.
반례
6 1 2
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
3 4
3 4 2 5
정답 4
5. 런타임 에러 (TypeError)
만약 승객을 태우고 목적지를 찾는 함수를 사용하시는 분들 중에 TypeError가 발생한다면 retrurn 값이 있는지 확인해보세요 저는 if문에서나 while문 안에서 반드시 끝날줄 알고 retrurn을 안넣어 주었더니 TypeError가 발생했었습니다.
6. 아마 80퍼에서 '틀렸습니다'가 발생한다면 여기서문제가 생긴 것입니다. 바로 손님을 태웠고 연료가 다 떨어진 칸의 주위가 벽으로 둘러 싸인 경우입니다.
목적지를 찾는 BFS함수에서 연료가 바닥난 시점이 벽으로 둘러 싸여있으면 큐에 다음 칸을 못넣어 큐가 비어있어 더 이상 BFS를 진행 못하고 while을 빠져나가게 됩니다. 여기서 -1을 출력하고 종료를 시켜야합니다.
다음의 반례를 통해 -1이 나오는지 확인해보세요
반례
6 1 19
1 0 0 0 1 0
1 0 1 0 1 1
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
4 2 1 6
정답 -1
제출 코드
from collections import deque
def findDest(x, y, fuel, destX, destY):
g = [i[:] for i in wall]
q = deque([])
q.append([x, y, fuel])
while q:
x, y, f = q.popleft()
g[x][y] = f
if f <= -1:
print(-1)
exit(0)
if x == destX and y == destY:
result = (fuel - f) * 2 + f
return result
for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):
nx, ny = x+dx, y+dy
if nx < 0 or nx >= N or ny < 0 or ny >= N or g[nx][ny] == -1:
continue
if g[nx][ny] == 0:
g[nx][ny] = f-1
q.append([nx, ny, f-1])
print(-1)
exit(0)
return
def BFS(tx, ty, fuel):
visited = [[0]*N for _ in range(N)]
g = [i[:] for i in Cgraph]
q = deque([])
q.append([tx, ty, fuel])
custList = [] # 같은 거리에 있는 손님들 리스트
findCust = False
minFuel = fuel
if g[tx][ty] == -2:
link = startLink[tx][ty]
destX, destY = endLink[link]
f = findDest(tx, ty, fuel, destX, destY)
Cgraph[tx][ty] = 0
return destX, destY, f
while q:
x, y, f = q.popleft()
if f <= -1:
print(-1)
exit(0)
#택시의 위치랑 손님의 위치랑 같을 떄
#같은 거리에 있는 손님들 다 찾기 반례 : 왼왼왼 보다 오오위 가 더 우선
visited[x][y] = 1
g[x][y] = f
for dx, dy in (-1, 0), (0, -1), (0, 1), (1, 0): # 행 번호 > 열 번호 낮은 순서
nx, ny = x + dx, y + dy
if nx < 0 or nx >= N or ny < 0 or ny >= N or g[nx][ny] == -1:
continue
if g[nx][ny] == 0 and not visited[nx][ny]:
g[nx][ny] = f - 1
q.append([nx, ny, f - 1])
# 같은 거리 손님 있는지 있으면 행 과 열 낮은 순 찾기
if startLink[x][y] != 0 and findCust and minFuel == f:
custList.append([x, y])
if f < minFuel and findCust:
custList.sort()
link = startLink[custList[0][0]][custList[0][1]]
destX, destY = endLink[link]
startx, starty = custList[0][0], custList[0][1]
f = findDest(startx, starty, minFuel, destX, destY)
startLink[startx][starty] = 0
return destX, destY, f
# 가까운 손님 찾았다면
if startLink[x][y] != 0 and not findCust:
minFuel = f
findCust = True
custList.append([x, y])
#마지막 칸에 존재한다면
if custList and not q:
link = startLink[custList[0][0]][custList[0][1]]
destX, destY = endLink[link]
startx, starty = custList[0][0], custList[0][1]
f = findDest(startx, starty, minFuel, destX, destY)
startLink[startx][starty] = 0
return destX, destY, f
print(-1)
exit(0)
N, M, fuel = map(int, input().split())
# 손님 정보까지 있는 그래프
Cgraph = []
for i in range(N):
temp = list(map(int, input().split()))
if 1 in temp:
for j in range(N):
if temp[j] == 1:
temp[j] = -1
Cgraph.append(temp)
wall = [i[:] for i in Cgraph]
tx, ty = map(int, input().split())
startLink = [[0, 0] * N for i in range(N)]
endLink = [[] for i in range(M+1)]
for i in range(1, M+1):
cx, cy, dx, dy = map(int, input().split())
startLink[cx-1][cy-1] = i
endLink[i] = [dx-1, dy-1]
#그냥 BFS로 손님 탐색
tx, ty = tx-1, ty - 1
for i in range(M):
tx, ty, fuel = BFS(tx, ty, fuel)
print(fuel)
제출 결과
후기
위 문제를 실제 시험장에서 만난다면 정말 끔찍할 것 같습니다. 차라리 문제가 어려워서 넘어가고 다른 문제를 푸는 전략을 세울 수 있지만 위 문제는 쉽다고 생각하여 섣불리 풀었다가 반례를 찾는데 시간을 다 소비할 것 같기 때문입니다.
그래도 다른사람의 코드를 베껴서 풀지 않고 반례만으로 코드의 문제점을 하나하나 찾아 풀어서 기분이 좋고 디버깅으로 문제를 해결해서 그 동안의 고통이 다 씻겨 내려졌습니다.
그래도 이런 문제는 다신 안 봤으면 좋겠습니다.
23년 4월 업데이트
백준에서 제 글이 생각보다 인기가 좋더라구요..
그래서 오랜만에 제 글을 읽었는데 음... 제가 크게 잘못되었다는 생각을 했습니다.
일단 반례를 찾아 나선다는건 제가 코드를 완벽하게 구현하지 못했다는 생각을 못하고 문제 탓만 했던 것 같습니다. 그쳐 김태희 교수님?
저 문제를 풀 때는 알린이라 저 문제가 매우 어렵고 까다롭다고 생각을 해서 저 문제만 풀었을 때 세상을 다 얻은 것 같았습니다.
그리고 제가 저런 문제는 다신 안보고 싶다 그랬죠..
그런데.. 지금 돌이켜 생각해보니..
삼성 A형 출제자님... 제발 다시 이런 문제만 내주시면 안될까요? 제가 잘못했습니다...
지금 A형 문제들은 너무 어렵습니다.. 제가 무지 몽매했습니다.. 제발 다시 저 수준의 시뮬레이션으로 돌려주세요..
시험장에서 다신 안보고 싶다는 말도 취소하겠습니다. 저런 문제만 보고싶습니다..ㅠㅠㅠ
B형 따고 다시 돌아오겠습니다.. 삼성을 준비하는 모든 취준생들.. 화이팅입니다..
삼성전자 가고싶다..
'ProblemSolving > BFS, DFS, 백트래킹' 카테고리의 다른 글
| 백준 11720 연결 요소의 개수 (파이썬) (0) | 2022.05.03 |
|---|---|
| SWEA 2814 최장경로 파이썬 (0) | 2022.04.30 |
| 백준 17142 연구소 3 (Python) (0) | 2022.04.12 |
| 백준 14501 퇴사 (Python) (0) | 2022.04.07 |
| 백준 15683 감시 (Python) (0) | 2022.03.31 |