[프로그래머스/Python] 방의 개수

방의 개수

🔍 알고리즘 분류

• 그래프

💡 문제 풀이

고려해야 할 문제
1. 같은 점을 다른 경로를 통해 돌아오는 것이 아니라 그냥 같은 길을 왕복해서 돌아올 수 있음
-> 간선을 따로 저장
2. 대각선이 교차할 때
-> 간선의 길이를 0.5로 설정하여 한 방향으로 두 번 나아가기

1. 방문한 점을 저장하는visited_nodes와 지나온 간선을 저장하는 visited_edges 생성
   • 점을 그냥 왕복해서 돌아올 수 있으므로 점만으로는 방의 개수를 판별할 수 없음
   • visited_edges는 무방향 간선 그래프로 설정
2. 대각선 교차를 고려하여 한 방향으로 나아가는 것을 총 2번 진행
3. 나아갈 점이 노드 셋에 있고, 나아갈 간선이 간선 셋에 없으면 정답에 1 추가
4. 노드 셋과 간선 셋에 새로운 점과 경로 추가

📄 코드

• Python

def solution(arrows):
    answer = 0
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    x, y = 0, 0
    visited_nodes = set()
    visited_edges = set() # 같은 길 왕복하는 경우도 있을 수 있으므로 간선까지 고려
    visited_nodes.add((x, y))
    
    for d in arrows:
        for _ in range(2): # 대각선 교차 고려해서 0.5 길이씩 두 번
            nx = x + dx[d]
            ny = y + dy[d]
            # 새로운 경로로 노드 다시 방문한 경우
            if ((x, y), (nx, ny)) not in visited_edges:
                if (nx, ny) in visited_nodes:
                    answer += 1
            visited_nodes.add((nx, ny))
            # 무방향 간선
            visited_edges.add(((x, y), (nx, ny)))
            visited_edges.add(((nx, ny), (x, y)))
            x, y = nx, ny
    
    return answer