[Summer/Winter Coding(~2018) / 프로그래머스] 49994번 : 방문길이

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

 

Lv2. 문제이다!

풀이를 진행하면서 놓쳤던 부분이 크게 두 부분이 있는데, 

1. 경로를 양방향이 아닌 단방향으로 생각했기에 a 점 -> b점 가는 건 거를 수 있어도, b점 -> a점으로 가는 경우는 거르지 못해서 틀린 답을 도출할 수 있다

그래서 조건을 만족하는 경로를 roots에 추가할 때 [(x,y), (nx,ny)] 와 [(nx,ny), (x,y)] 모두 추가해야한다

 

2. 다음 지점인 nx,ny 설정에 미흡했다. 

문제 조건에서는 (-5,-5) ~ (5,5) 외로 이동할 경우에는 그 이동은 무시하고, 유효한 이동을 이어나가면 된다고 했다

2-1.  nx, ny가 범위를 벗어난다면 nx, ny를 x,y(이전 지점)으로 옮기고 다시 범위 안으로 들어올 때까지 반복문을 돌린다

2-1.  nx,ny가 범위에 있다면 이를 다시 시작점으로 옮기면 된다 

 

풀이 이해 

1. dirs의 문자에 해당하는 이동 좌표를 directions에 설정한 후 진행한다

2. dirs의 0인덱스 문자를 꺼낸 후 문자에 해당하는 만큼 이동한다

3. nx,ny가 범위 내이고, 이전에 가보지 않았던 경로라면 count += 1을 해준다

4. nx,ny가 범위 내이지만, 이전에 가봤던 경로라면 count 값에 변화를 주지 않고 routes에 경로 추가만 하고, 이동한 값을 출발값으로 설정한다

5. nx,ny가 범위 외라면 움직이기 전 값으로 재설정해준다

6. 처음가는 경로만 센 count를 반환한다 

 

-정답 풀이 :

def solution(dirs):
    #(from, to) 
    routes = []
    directions = {'U': (0, 1), 'D': (0, -1), 'R' : (1, 0), 'L' : (-1, 0)}
    dirs = list(dirs)
    
    count = 0
   
    x,y = 0,0
    while dirs:        
        d = dirs.pop(0)
        nx, ny = x + directions[d][0], y + directions[d][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            if [(x,y), (nx,ny)] not in routes:
                count += 1
            routes.append([(x,y), (nx, ny)])     
            routes.append([(nx, ny), (x,y)]) 
            x, y = nx,ny
        else:
            nx, ny = x, y
            continue
    
    return count

 

- 시도해본 풀이 :

35%에서 막혔다 

위에서 언급한 문제들 때문에 막혔던 것 같다   

def solution(dirs):
    #(from, to) 
    roots = []
    directions = {'U': (0, 1), 'D': (0, -1), 'R' : (1, 0), 'L' : (-1, 0)}
    dirs = list(dirs)
    
    d = dirs.pop(0)
    roots.append([(0,0), (directions[d][0], directions[d][1])])
    x, y = directions[d][0], directions[d][1]
    count = 1
    
    while dirs:        
        d = dirs.pop(0)
        x, y = roots[-1][1][0], roots[-1][1][1]
        nx, ny = x + directions[d][0], y + directions[d][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            if [(x,y), (nx,ny)] not in roots:
                count += 1
            roots.append([(x,y), (nx, ny)])                
        else:
            continue
    
    return count