문제
https://school.programmers.co.kr/learn/courses/14760/lessons/125479#
-
현수는 송아지를 잃어버렸습니다. 다행히 송아지에는 위치추적기가 달려 있습니다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동합니다. 송아지는 움직이지 않고 제자리에 있습니다.
-
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 현수의 위치 s와 송아지의 위치 e가 주어지면 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 최소 점프의 횟수는 1이상입니다.
-
입출력 예시
-
제한사항
• 수직선 상의 좌표는 1부터 10,000까지입니다.
• s와 e는 같은 값으로 입력되지 않습니다.
오류 수정 과정
- 강의 수강 후, 처음 코드를 작성했을 때 하나의 테스트 케이스에 관해서 오류가 발생했었다. 아무리 봐도 런타임이 초과될 부분이 없어서 정답 코드와 비교를 해보았는데, 뜻밖의 부분에서 해당 오류가 나타나는 것이었다. (모든 부분을 바꿔가면서 비교해봤는데 런타임 에러가 직접적으로 발생하는 부분이 여기밖에 없었음)
방문하지 않았던 노드인지와 nx가 좌표의 최대&최솟값 사이에 들어오는 값인지를 확인하는 if문
정답
if nx > 0 and nx <= 10000 and check[nx]==0: check[nx] = 1 queue.append(nx)런타임 에러
if check[nx] == 0 and nx > 0 and nx <= 10000: # 방문하지 않았던 노드이고, 최대&최소 좌표범위 내에 들어오면 check[nx] = 1 queue.append(nx)
- nx > 0 and nx <= 10000 과 check[nx] == 0 의 순서에 의해 런타임 에러가 발생하거나 발생하지 않는 것이다.
- 그 이유는 아직 모르겠다.. 혹시 아시는 분이 있다면 댓글로 알려주시면 감사하겠습니다 🙇🏻♀️
코드
정답 코드 (오류 수정 완료)
- 아래 런타임 에러 코드에 대해 오류 수정을 완료한 코드이다.
from collections import deque
def solution(s, e):
answer = 0
check = [0]*10001
queue = deque()
queue.append(s)
check[s] = 1
L = 0
while(queue):
length = len(queue)
for _ in range(length):
x = queue.popleft()
for nx in [x-1, x+1, x+5]:
if nx == e:
return L+1
if nx > 0 and nx <= 10000 and check[nx]==0: # 오류가 발생했던 부분
check[nx] = 1
queue.append(nx)
L += 1실행 결과
런타임 에러 (수정 중)
- 아래 코드가 틀린 이유를 알아내었다.
만약 check[nx] == 0을 앞에 쓰게 되면, 전체 수직선을 넘어가는 값에 대해서도 check 배열의 값을 확인하게 된다. 하지만, 전체 수직선을 초과하는 값에 대해서는 check 배열을 확인할 필요가 없다. 따라서 다음과 같이 작성해주어야 한다.
if nx > 0 and nx <= 10000 and check[nx]==0:
check[nx] = 1
queue.append(nx)또는 다음과 같이도 작성 가능하다.
(다음처럼 작성하는 것이 직관적이며 더욱 좋을 것 같다.)
if nx > 0 and nx <= 10000:
if check[nx]==0:
check[nx] = 1
queue.append(nx)- 추가로 파이썬에서는 대소 비교를 0 < nx <= 10000 과 같이 작성 가능하다.
* 아래 작성한 코드가 한 개의 테스트 케이스에 대해서 런타임 에러가 발생해 수정 중이다. (수정 완료)
from collections import deque
def solution(s, e):
check = [0]*10001 # 1~10000까지의 좌표 번호 (방문 여부 체크 배열)
queue = deque()
queue.append(s) # 현수의 처음 위치를 큐에 삽입
check[s] = 1 # 처음 넣은 값도 방문여부 체크해줘야 함 (안해서 런타임에러 발생했었음)
L = 0 # BFS의 현재 레벨 (정답을 담는 변수)
while(queue):
length = len(queue)
for _ in range(length):
now = queue.popleft() # queue에 들어있는 숫자들을 하나씩 모두 pop하면서 이동 후의 좌표 값을 구함
for nx in [now-1, now+1, now+5]:
if nx == e:
return L+1 # 다음 노드가 e와 같으면, queue에 넣지 않고도 바로 Level에 1 추가한 값을 리턴 (넣고 빼서 발견하지 말기)
if check[nx] == 0 and nx > 0 and nx <= 10000: # 방문하지 않았던 노드이고, 최대&최소 좌표범위 내에 들어오면
check[nx] = 1
queue.append(nx) # 해당 노드로 이동
L += 1 # 레벨 증가시킴 (다음 레벨로 넘어감)실행 결과
👩🏻💻 AI를 좋아하는 IT학부생