[프로그래머스][level5] 방의 개수 - python

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/49190

코딩테스트 연습 - 방의 개수

 

풀이 - 다른 블로그 참고 

방의 개수 세는 방법 : 현재 경로가 기존에 만들어진 적이 없으면서, 하나의 정점을 재방문 하는 경우 

 

따라서 이동 방향에 따라 이동하면서,

재방문하는 정점이고 현재 경로가 기존에 만들어진적이 없으면 방의 개수 + 1

처음 방문하는 정점이면, 경로 추가 

 

단, 두 칸씩 이동하면서 검사를 해야 예외 case를 해결할 수 있다. 

- https://pf333.tistory.com/86 참고 

from collections import defaultdict 

def solution(arrows):
    answer = 0
    # 경로 추가할 list 
    visited = defaultdict(list)
    
    # 번호에 따른 이동 방향 
    dx = [ -1, -1, 0, 1, 1, 1, 0, -1 ]
    dy = [ 0, 1, 1, 1, 0, -1, -1, -1 ]
    # 처음 위치 
    x,y = 0,0
    
    for arrow in arrows :
    	# 예외 case 해결을 위해 2칸 씩 검사해줘야 함 
        for _ in range(2):
            nx = x + dx[arrow]
            ny = y + dy[arrow]
            
            # 방문했던 정점이지만, 겹치는 경로가 아닌 경우
            if (nx,ny) in visited and (x,y) not in visited[(nx,ny)]:
            	# 방의 개수 + 1
                answer += 1 
                visited[(x,y)].append((nx,ny))
                visited[(nx,ny)].append((x,y))
            # 방문하지 않은 정점인 경우
            elif (nx,ny) not in visited:
                # 경로 추가 
                visited[(x,y)].append((nx,ny))
                visited[(nx,ny)].append((x,y))
            # 위치 갱신 
            x,y = nx,ny
            
    return answer