프로그래머스(programmers) 방의 갯수 python 정답[Graph]

프로그래머스(programmers) 방의 갯수 python 정답[Graph 알고리즘]

문제 링크

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

프로그래머스

문제 정답

from collections import defaultdict
def solution(arrows):
    visited = defaultdict(set)
    cy,cx ,answer= 0,0,0
    d = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(1,1)]
    for arrow in arrows:
        for _ in range(2): 
            # 엣지 케이스 : 모래시계 모양 회피 위해 가운데 점을 만드는 효과
            dy,dx = d[arrow]
            ny,nx = cy +dy,cx +dx
            # 방문한 적이 있는 점인데, 새로운 곳에서 들어오는 경우 방이 하나 더 생긴다.
            if (ny,nx) in visited and  (cy,cx) not in visited[(ny,nx)]:
                answer +=1     
            visited[(ny,nx)].add((cy,cx))
            visited[(cy,cx)].add((ny,nx))                                
            cy,cx = ny,nx
    
    return answer

 

 

이 문제는 몇 가지 아이디어가 중요하다.

오일러 방정식을 써도 된다는데, 코딩테스트는 무엇보다 일반적인 구현을 연습하는게 중요하다.

1. 방문한 점을 다시 방문하면 방이 생긴다.

• 이때 왔던 방향에서 다시 오는 경우는(그려진 선을 다시 그림) 제외한다.
• 해당 점을 튜플 객체를 해시로, 해당 튜플에 해당하는 밸류를 집합으로 구성하여, 해당 점으로 들어오는 점을 모아둔다
  
  • 딕셔너리에 튜플이 있으면 방문한 것이다
  • 해당 튜플을 키로 꺼내온 밸류(집합)를 이용해 해당 점으로 진입하려는 점이 이전에 방문한 적이 있는 점인지 판단한다.

2. 엣지 케이스를 고려하여 좌표를 2배로 키운다

한 칸씩 이동하면 아래와 같이 중간점에서 교차하는 케이스를 잡아내지 못한다. (정수 지점이 아니기 때문)

이동거리를 두 배 해주면, 1의 중간 지점인 1/2가 1이 되어 로직을 통해 캐치해 낼 수 있다.

출처: https://bellog.tistory.com/147