[프로그래머스] 파이썬 python - 방문 길이

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

프로그래머스

Level 2. 방문 길이

Summer/Winter Coding(~2018) 

 

접근 방식
1. dirs을 돌면서, 방문 경로를 차례대로 저장한다. 이때, 유효한 좌표평면인지 확인한다. 
  나의 경우에는 가장 최근의 좌표를 알기 위해 stack을 사용하였다. 
2. 그 후 스택을 다시 반복하면서 해당 경로에 온적 있는지 확인한다.
   이 경우에는 중복을 확인하기 위해 set을 사용하였으며, 중요한 점(!!!)은 반대 방향까지 확인해야 한다.

 

시행착오 1. 

from collections import deque
dirs = "ULURRDLLU"

def isvalid(x,y) :
    if x<-5 or y<-5 or x>5 or y>5:
        return False
    else:
        return True

def solution(dirs):
    answer = 0
    
    road = deque()
    now = ((0,0))
    road.append(now)
    for d in dirs:
        nowx, nowy = road[-1]
        print(d, nowx, nowy)
        
        if d == 'U':
            if isvalid(nowx, nowy+1) == False:
                continue
                
            elif isvalid(nowx, nowy+1) == True:
                if ((nowx,nowy+1)) in road:
                    continue
                else:
                    road.append((nowx, nowy+1))
                    
                
        elif d == 'D':
            if isvalid(nowx, nowy-1) == False:
                continue
            elif isvalid(nowx, nowy-1) == True:
                if ((nowx, nowy-1)) in road:
                    continue
                else:
                    road.append((nowx, nowy-1))
            
        elif d == 'R' :
            if isvalid(nowx+1, nowy) == False:
                continue
            elif isvalid(nowx+1, nowy) == True:
                if((nowx+1, nowy)) in road:
                    continue
                else:
                    road.append((nowx+1, nowy))
            
        elif d == 'L' :
            if isvalid(nowx-1, nowy) == False:
                continue
            elif isvalid(nowx-1, nowy) == True:
                if ((nowx-1, nowy)) in road:
                    continue
                else:
                    road.append((nowx-1, nowy))
       
    print(len(road))
    answer = len(road)-1
    
    return answer


print(solution(dirs))

시행착오 1. 그냥 좌표만 집어넣었었는데 이러니까 당연히 절대 안됨

 

시행 착오 2.

from collections import deque

def isvalid(x,y) :
    if x<-5 or y<-5 or x>5 or y>5:
        return False
    else:
        return True

def solution(dirs):
    
    road = deque()
    
    if dirs[0] == 'U':
        road.append((0,0,0,1))
    elif dirs[0] == 'D':
        road.append((0,0,0,-1))
    elif dirs[0] == 'R':
        road.append((0,0,1,0))
    elif dirs[0] == 'L':
        road.append((0,0,-1,0))
        
    dirs = dirs[1:]
    
    for d in dirs:
        nowx, nowy = road[-1][2], road[-1][3]
        
        if d == 'U':
            if isvalid(nowx, nowy+1) == False:
                continue
            elif isvalid(nowx, nowy+1) == True:
               road.append((nowx, nowy, nowx, nowy+1))
                    
                
        elif d == 'D':
            if isvalid(nowx, nowy-1) == False:
                continue
            elif isvalid(nowx, nowy-1) == True:
                road.append((nowx, nowy, nowx, nowy-1))
            
        elif d == 'R' :
            if isvalid(nowx+1, nowy) == False:
                continue
            elif isvalid(nowx+1, nowy) == True:
                road.append((nowx, nowy, nowx+1, nowy))
            
        elif d == 'L' :
            if isvalid(nowx-1, nowy) == False:
                continue
            elif isvalid(nowx-1, nowy) == True:
                road.append((nowx, nowy, nowx-1, nowy))
    
    road = set(road)
    road = list(road)
    return len(road)

 

이제야 아! set에 넣으면 자동으로 중복을 제거할 수 있겠구나 생각했다.

근데 더 생각해보니까.. 반대 방향이 있다는 것을 까먹고 있다는 것을 깨달음. 

 

최종 코드

from collections import deque

def isvalid(x,y) : #유효한 좌표평면인지 확인
    if x<-5 or y<-5 or x>5 or y>5:
        return False
    else:
        return True

def solution(dirs):
    
    road = deque()
    
    if dirs[0] == 'U': #최초 방문 road에 append
        road.append((0,0,0,1))
    elif dirs[0] == 'D':
        road.append((0,0,0,-1))
    elif dirs[0] == 'R':
        road.append((0,0,1,0))
    elif dirs[0] == 'L':
        road.append((0,0,-1,0))
        
    dirs = dirs[1:] #초기 방문은 확인했으니 그 후부터 확인한다
    
    for d in dirs:
        nowx, nowy = road[-1][2], road[-1][3] 
        
        if d == 'U':
            if isvalid(nowx, nowy+1) == False: #유효하지 않다면 해당 방문은 무시한다
                continue
            elif isvalid(nowx, nowy+1) == True: #유효하다면 방문 경로를 일단 저장한다
               road.append((nowx, nowy, nowx, nowy+1))
                
        elif d == 'D':
            if isvalid(nowx, nowy-1) == False:
                continue
            elif isvalid(nowx, nowy-1) == True:
                road.append((nowx, nowy, nowx, nowy-1))
            
        elif d == 'R' :
            if isvalid(nowx+1, nowy) == False:
                continue
            elif isvalid(nowx+1, nowy) == True:
                road.append((nowx, nowy, nowx+1, nowy))
            
        elif d == 'L' :
            if isvalid(nowx-1, nowy) == False:
                continue
            elif isvalid(nowx-1, nowy) == True:
                road.append((nowx, nowy, nowx-1, nowy))
    
    set_road = set() #set 생성
    for r in road:
        oldx, oldy, newx, newy = r #현재는 방향이 존재하는 방문 경로를 저장해둠
        
        if (oldx, oldy, newx, newy) in set_road or (newx, newy, oldx, oldy) in set_road: #반대 방향까지 확인한다.
            continue
        else:
            set_road.add((oldx, oldy, newx, newy))
    
    
    return len(set_road)

최종 코드는 위와 같다.

 

그래도 생각보다 쉽게 풀었는데, 아주 잘 푼 코드인지는 모르겠다. 그래도 바로 내가 무엇을 잘못하고 있는지를 바로 깨닫고 고칠 수 있었음에..... 감사하며....

무슨 알고리즘인지 생각해본다면,, 아마 구현이 아닐까 싶다. 문제에서 말하는 그대로 코드로 작성할 수 있는지를 묻는 것 같다. 공부를 열심히 해야지..........