[Python] 프로그래머스 Lv.02 - 방문 길이

programmers.co.kr/learn/courses/30/lessons/49994

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

[ 알고리즘 ]

구현

 

[문제 접근]

시작 좌표와 끝 좌표가 visited 배열에 존재한다면 이미 방문한 길 이라고 생각하고 구현하였음

여기서 주의해야할 점은 되돌아 가는 경우도 고려해야한다는 점이다.

예를들어 (0,0)->(5,5) 로 가는 경로를 (0,0,5,5) 이런 형태로 visited 배열에 저장해주었는데 이렇게 되면 (5,5)->(0,0)으로 가는 경로를 인식을 못해서 뒤집어서 (5,5,0,0) 도 같이 저장해주었다.

 

쌩으로 구현한거라 다른 더 좋은 방법이 존재할 것 같기도..

 

[코드]

from collections import deque
def solution(dirs):
    que=deque()
    cnt = 0
    
    graph=[[0]*11 for i in range(11)]
    
    visited=[]
    
    que.append((5,5)) #5,5에서 시작
    
    for i in dirs:
        x,y=que.popleft() # 현재 위치
        
        if i=='U':            
            if x-1<0 or y<0 or x-1>10 or y>10:
                que.appendleft((x,y))
                continue
                        
            if (x,y,x-1,y) not in visited and (x-1,y,x,y) not in visited:
                cnt+=1
                
            que.append((x-1,y))
            visited.append((x,y,x-1,y))
            visited.append((x-1,y,x,y)) # 되돌아 가는 경우
                        
        elif i=='D':
            if x+1<0 or y<0 or x+1>10 or y>10:
                que.appendleft((x,y))
                continue
                
            if (x,y,x+1,y) not in visited and (x+1,y,x,y) not in visited:
                cnt+=1
                
            que.append((x+1,y))
            visited.append((x,y,x+1,y))
            visited.append((x+1,y,x,y))
        
        elif i=='L':
            if x<0 or y-1<0 or x>10 or y-1>10:
                que.appendleft((x,y))
                continue
                
            if (x,y,x,y-1) not in visited and (x,y-1,x,y) not in visited:
                cnt+=1
                
            que.append((x,y-1))
            visited.append((x,y,x,y-1))
            visited.append((x,y-1,x,y))
            
        elif i=='R':
            if x<0 or y+1<0 or x>10 or y+1>10:
                que.appendleft((x,y))
                continue
                
            if (x,y,x,y+1) not in visited and (x,y+1,x,y) not in visited:
                cnt+=1
                
            que.append((x,y+1))
            visited.append((x,y,x,y+1))
            visited.append((x,y+1,x,y))
                
    return cnt