[Programmers] 방문 길이 (Python)

코딩테스트 연습 - 방문 길이

 

처음에는 매 칸의 상하좌우로 방문한 곳을 다 저장해야하나 하고 생각해서 매우 어렵게 접근했었다..🥲

하지만 뮤.뮤가 매우 간단한 아이디어를 제공해줬다!!

 

이 문제의 핵심은 바로 "선을 어떻게 표현할 수 있는가?" 이다!

이 문제에서 선은 어떻게 만들어지는가!

바로 점과 점이 만나서 선이 만들어진다.

즉, (출발점, 도착점) 정보가 바로 선에 대한 정보인것!

 

따라서 (출발점, 도착점) 정보가 총 중복 없이 몇 개 있느냐가 정답이된다!

나같은 경우 (출발점) : [(도착점)]을 저장하는 딕셔너리를 만드는 방식으로 구현했다.

이때 (출발점, 도착점)과 (도착점, 출발점)은 동일한 선이므로 각각 딕셔너리에 저장한 후 마지막에 2로 나누어 주어야 한다!

 

 

from collections import defaultdict

def check_pos(x, y) :
    if 0 <= x <= 10 and 0 <= y <= 10 :
        return True
    return False

def solution(dirs):
    answer = 0
    history = defaultdict(set)
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    dir_dict = {"U" : 0, "D" : 1, "L" : 2, "R" : 3}
    
    x, y = 5, 5
    for dir in dirs.strip() :
        idx = dir_dict[dir]
        nx, ny = x + dx[idx], y + dy[idx]
        if check_pos(nx, ny) :
            history[(x, y)].add((nx, ny))
            history[(nx, ny)].add((x, y))
            x, y = nx, ny
    for value in history.values() :
        answer += len(value)
    return answer // 2