[ Lv 5 ] [ 그래프 ] 방의 개수

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

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

---

풀이 과정

---

1. 방으로 셀수있는 경우의 수는 두가지이다.

   • 대각선끼리 교차하는 경우
   • 지나가지 않은 간선으로 이미 방문한 노드를 다시 방문하게 될 때

2. 각각의 경우에 맞추어서 대각선끼리 교차할 때와 재방문할때 방의 개수를 하나씩 늘려주면 된다.

3. 여기서 해맸던 점이.. 한방향 방문 처리만 해주어서 다른 방향으로 다시 방문할때 방의 개수가 계속 늘어나게 되는 문제가 있었다.

   • 따라서, (a,b) -> (c,d)로 진행한다면, (c,d) -> (a,b)도 방문처리 해주어야 함.

---

소스 코드

---

def movement(x, y, arrow):
    if arrow == 7:
        x += 1
        y -= 1
    if arrow == 6:
        y -= 1
    if arrow == 5:
        x -= 1
        y -= 1
    if arrow == 4:
        x -= 1
    if arrow == 3:
        x -= 1
        y += 1
    if arrow == 2:
        y += 1
    if arrow == 1:
        x += 1
        y += 1
    if arrow == 0:
        x += 1
    return x, y

def cross_check(edge, x, y, arrow):
    if arrow == 1:
        if (x, y+1, x+1, y) in edge or (x+1, y, x, y+1) in edge:
            return True
    elif arrow == 5:
        if (x, y-1, x-1, y) in edge or (x-1, y, x, y-1) in edge:
            return True
    elif arrow == 7:
        if (x, y-1, x+1, y) in edge or (x+1, y, x, y-1) in edge:
            return True
    elif arrow == 3:
        if (x-1, y, x, y+1) in edge or (x, y+1, x-1, y) in edge:
            return True

    return False


def solution(arrows):
    answer = 0
    visited = set()
    edge = set()
    x, y = 0, 0
    visited.add((x, y))
    for arrow in arrows:
        currentX, currentY = x, y
        x, y = movement(x, y, arrow)

        # 교차하는 대각선 여부 확인
        if arrow in [1, 3, 5, 7] and cross_check(edge, currentX, currentY, arrow):
            if (x, y, currentX, currentY) not in edge: 
                answer += 1

        if (x, y) in visited:
            # 반대로 돌아오는 간선 있는지 체크
            if (x, y, currentX, currentY) not in edge: 
                answer += 1
        else:
            visited.add((x, y))

        # 현재 간선정보 저장
        edge.add((currentX, currentY, x, y))
        edge.add((x, y, currentX, currentY))
    return answer