프로그래머스 (방의 개수) with python

• 문제 설명

원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다.

ex) 1일때는 오른쪽 위로 이동

그림을 그릴 때, 사방이 막히면 방하나로 샙니다.
이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요.

제한사항

• 배열 arrows의 크기는 1 이상 100,000 이하 입니다.
• arrows의 원소는 0 이상 7 이하 입니다.
• 방은 다른 방으로 둘러 싸여질 수 있습니다.

• 문제 풀이

이 문제를 풀이 시 고려해야 할 조건들이 여러 가지가 있다

먼저 풀이의 프로세스를 따졌을 때는 크게 두 가지로 나눌 수 있다

노드와 노드를 연결하는 선들을 세팅하는 작업 1가지, 

세팅된 것들을 이용하여 방이 몇 개 그려지는지 확인하는 작업 1가지이다

이를 구체화하면,

1. 방향에 따른 x,y 설정 작업과, 이동 경로를 사전 자료형으로 정의하고 배열로 들어온 값들을 확인하여 해당 노드들을 그어준다 즉 좌표와 노드를 함께 저장해준다 노드의 정방향,반대방향도 신경써준다 모래시계형을 통해 교차하는 것도 신경써준다 (노드량을 두 배로 늘린다)   2. bfs 방법을 통하여 첫 번째부터 돌면서 이전에 방문한 적이 있는 좌표이면서  한번도 방문하지 않은 노드인 것을 찾아낸다

 

from collections import deque
dx=[0,1,1,1,0,-1,-1,-1]
dy=[1,1,0,-1,-1,-1,0,1]
def solution(arrows):
    answer=0
    # 사전형을 통한 노드,좌표 설정
    node,point,q={},{},deque()
    point[(0,0)]=0
    q.append([0,0])
    x,y=0,0

    for i in arrows:
        for _ in range(2): # 모래시계형을 고려해주기 위해 point를 두 배로 늘린다
            nx=x+dx[i] #x,y를 방향에 따라 늘려준다 
            ny=y+dy[i]
            point[(nx,ny)]=0 # 좌표값을 설정해준다
            q.append([nx,ny])
            node[(x,y,nx,ny)]=0
            node[(nx,ny,x,y)]=0
            x,y=nx,ny
    
    x,y=q.popleft()
    point[(x,y)]=1 # 맨 처음에는 1을 넣어준다
    while q:
        nx,ny=q.popleft()

        # 이전에 방문한 적이 있는 경우
        if point[(nx,ny)]==1:
            # 한 번도 방문한 적이 없는 노드인 경우
            if node[(x,y,nx,ny)]==0:
                answer+=1
                node[(x,y,nx,ny)]=1 # 노드를 방문한 것으로 바꿔준다
                node[(nx,ny,x,y)]=1
        else:
            # 이전에 방문한 적 없는 경우
            point[(nx,ny)]=1
            node[(x,y,nx,ny)]=1
            node[(nx,ny,x,y)]=1
        x,y=nx,ny

    return answer