방문길이 [프로그래머스]

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

 

 

코테 준비를 하면서 슬슬 정리를 하면서 해야할꺼 같다. 슬슬 기초적인건 구현할 수 있는데 이해 안가는건 좀 소화를 시켜야 할듯 

 

문제 설명 

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

U: 위쪽으로 한 칸 가기
D: 아래쪽으로 한 칸 가기
R: 오른쪽으로 한 칸 가기
L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

 

입출력예시 

dirs	answer
"ULURRDLLU"	7
"LULLLLLLU"	7

 

결론적으로는 앞서 간길을 돌아오는건 카운팅하지 않고 -5 <= x <= 5 . -5 <=y<=5 범위내에서만 갈 수 있다. 

visited = set()

이미 지난 길(간선)들을 담아 중복을 막는 집합.

x, y = 0, 0

시작 블럭 좌표 

mov ={'U':(0,1),'D':(0,-1),'R':(1,0),'L':(-1,0)}

움직임을 dict에 저장 

for i in dirs:
    dx, dy = mov[i]
    nx, ny = x+dx, y+dy

nx, ny에 움직인만큼의 x,y가 움직인 거리 더해줌 

if -5<=nx<=5 and -5<=ny<=5:

nx,ny가 범위를 넘어가지 않을때 결정해줌 

path = sorted([(x,y),(nx,ny)])
visited.add(tuple(path))

여기가 킥인데 일단 우리는 edge를 찾는 중 따라서 기존 점 (0,0 ) -> (1,0) 이게 하나의 간선 

즉 이전 점과 이후 점을 저장해줘야 함 그리고 (1,0) -> (0,0)은 이전의 길을 돌아가는것 따라서 sort로 무방향의 간선으로 만든다. 

그후 방문했던 edge를 set에 넣어준다. set에 넣으려면 tuple로 감싸줘야 함 

x, y = nx, ny
return len(visited)

그 후 x,y를 nx와 ny로 바꿔주고 개수의 길이를 return 한다. 

 

정답 

def solution(dirs):
    visited = set()

    x, y = 0, 0

    mov ={'U':(0,1),'D':(0,-1),'R':(1,0),'L':(-1,0)}

    for i in dirs:
        dx, dy = mov[i]
        nx, ny = x+dx, y+dy

        if -5<=nx<=5 and -5<=ny<=5:
            path = sorted([(x,y),(nx,ny)])
            visited.add(tuple(path))
            x, y = nx, ny
            
    return len(visited)

 

여기서 길을 방향없는 간선임을 파악하는 것이 포인트 

솔직히 sorted전까지는 다 구현했느네 이 포인트를 구현 못했다.