들어가며
알고리즘 2주차 마무리 테스트 문제 중 하나인 '방문 기록'
심화트랙 알고리즘 주차에 들어온 이래로 직접 풀어낸 몇 안되는 문제였다. 물론 DFS/BFS 문제는 건들지도 못했지만...
뿌듯하니까 자랑하면서 들어가기로
문제
https://programmers.co.kr/learn/courses/30/lessons/49994
코딩테스트 연습 - 방문 길이
programmers.co.kr
입출력 예시
| dirs | answer |
| "ULURRDLLU" | 7 |
| "LULLLLLLU" | 7 |
생각과정
상하좌우로 움직이는 좌표를 딕셔너리와 튜플을 이용해서 구성하고, 지난 섬의 개수 강의에서 배웠던 것처럼 nx, ny 변수를 만들어 이용해보았다. 처음에는 지나간 부분을 len(visited)로 리턴값을 구하려고 했지만 테스트케이스 1번과 8 ~ 20번을 통과하지 못했다. 고민끝에 반례를 찾아보니 되돌아갔을 때의 예외처리도 해줘야한다는 걸 알게 되어서 결국 리턴값을 cnt로 카운트 해주고 되돌아갔을 때의 경우에도 visited에 넣어주기로 했다.
이 부분을 해결하고 나니 포인터가 그래프를 벗어났을 때의 예외처리가 문제였다.
코드를 일일히 지저분하게 짜고싶지 않아서 시도를 몇번 해봤지만 따로 방법이 떠오르지 않아 결국 아래 전체 코드처럼 작성했다!
풀이
def solution(dirs):
move = {'U': (0, 1), 'D': (0, -1), 'L': (-1, 0), 'R': (1, 0)}
visited = []
x, y = 0, 0
cnt = 0
for command in dirs:
# 이동하고자 하는 좌표
dx, dy = move[command]
# 그래프를 벗어났을 때 예외처리
if x > 5:
x = 5
if y > 5:
y = 5
if x < -5:
x = -5
if y < -5:
y = -5
# 이동한 좌표
nx, ny = x + dx, y + dy
# 갈 때
went = (x, y, nx, ny)
# 되돌아 올 때
back = (nx, ny, x, y)
# 방문 처리
if went not in visited and\
-5 <= x <= 5 and -5 <= y <= 5 and -5 <= nx <= 5 and -5 <= ny <= 5:
visited.append(went)
# 되돌아갔을 때도 저장
visited.append(back)
cnt += 1
x, y = nx, ny
return cnt
move 변수를 딕셔너리로 선언해주고 상하좌우 좌표를 미리 지정해주었다. 앞으로 사용될 녀석들을 초기화 해주고, for문으로 이동한 방향들을 하나씩 꺼내서 캐릭터를 움직여주기 시작한다.
그래프를 벗어났을 때의 예외처리가 깔끔하지 못하지만, 그래프는 아래 그림처럼 -5부터 5까지의 인덱스로 되어있으므로 각각의 좌표가 그래프를 탈출 했을 때 그 이상으로 넘어가지 않게 해주었다.
좌표를 이동해 줄 nx, ny 변수에 현재 x, y좌표 + 움직인 방향의 좌표를 해주고, 처음 나아갈 때의 went와 다시 되돌아올 때의 back을 선언해주었다. 이 부분이 반례를 잡을 때 중요했는데, back은 이미 갔던 길을 되돌아왔을 때 다시 횟수를 세는 일을 방지하기 위해 선언해주었다.
여기서 went와 back의 튜플 순서가 반대인데, 그 이유는 갈 때와 올 때의 좌표를 생각해보면 이해할 수 있다.
예를 들어 오른쪽으로 한칸 이동했다고 가정해보자. 현재 좌표는 (0, 0)이고 옮긴 좌표는 (1, 0)이다. 그리고 다시 왼쪽으로 돌아올 때 현재 좌표는 (1, 0)이고 옮긴 좌표는 (0, 0)이다. 간단쓰!
마지막으로 움직인 횟수를 + 1해주고, 현재 인덱스를 옮긴 인덱스로 옮겨주고 주어진 입력만큼 반복하면 해결!
마치며
튜플의 활용성이 생각보다 좋은 것 같다. 딕셔너리도 그렇고. 자료구조를 열심히 공부해야하는 이유가 점점 머리에 들어온다.
