[프로그래머스 lv 5] 방의 개수

사용 언어 - Python3

문제 - 방의 개수

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

프로그래머스

 

정답

대각선 판별을 위해 이동거리를 1이 아닌 2라고 생각하기

방문여부, 경로가 겹치지 않았는지 확인

 

0. from collections import defaultdict

: dic클래스의 서브 클래스, 유사딕셔너리

: 외부함수라 import 필요

 

visit = defaultdict(list) : 방문여부를 빈리스트로 유사딕셔너리로 설정

 

1. x,y에서 nx,ny로 이동하기

x,y = 0,0 # 시작 위치

dx = [0,1,1,1,0,-1,-1,-1] # 이동가능한 모든 방향

dy = [1,1,0,-1,-1,-1,0,1]

 

nx = x+dx[r] # 이동할 위치

ny = y+dy[r]

 

만약 대각선끼리 만나서 가운데에 점이 생긴 경우(=모래시계 모양), 도형은 삼각형 2개가 생성된다.

이런 경우를 대비하기 위해, 애초에 이동거리가 2라고 생각한다면(=똑같은 이동 2번 반복한다면), 대각선으로 이동하는 경우 고려할 수 있다.

x,y = nx,ny로 이동시키면서 방문처리를 해주면서 방이 생길 수 있는지 확인해준다.

 

2. 방이 생기는 조건

"기존에 방문하지 않은 경로이면서 현재 이동할 위치를 재방문하는 경우"

이동할 위치를 이미 방문했었고 (nx,ny) in visit

현재위치가 이동할 위치의 경로에 속하지 않았을 때(=경로가 겹치지 않았을 때) (x,y) not in visit[(nx,ny)]

방이 생긴다. answer += 1

방문처리

visit[(x,y)] => (nx,ny) x,y 위치에 nx,ny도 방문했다.

visit[(nx,ny)] => (x,y) nx,ny 위치에 x,y도 방문했다.

x,y와 nx,ny는 같은 방에서 방문했음을 의미(경로가 겹친다)

 

3. 처음 방문하는 곳인 경우 (nx,ny) not in visit

방문처리

 

4. return answer 방개수

 

from collections import defaultdict
def solution(arrows):
    answer = 0
    visit = defaultdict(list)    
    x,y = 0,0
    
    # 이동가능한 모든 경로
    dx = [0,1,1,1,0,-1,-1,-1]
    dy = [1,1,0,-1,-1,-1,0,1]
    
    for r in arrows:
        # 애초에 이동거리가 2라고 생각하면,
        # 중간에 1개 노드 = 대각선으로 이동하는 경우
        for _ in range(2): # 똑같은 이동 2번 하는 꼴
            nx = x+dx[r]
            ny = y+dy[r]
            # 방문했던 점, 경로가 겹치지 않았던 점 -> 방 생성
            if (nx,ny) in visit and (x,y) not in visit[(nx,ny)]:
                answer += 1 # 방 개수
                visit[(x,y)].append((nx,ny))
                visit[(nx,ny)].append((x,y))
            # 방문하지 않았던 점 -> 방문처리
            elif (nx,ny) not in visit:
                visit[(x,y)].append((nx,ny))
                visit[(nx,ny)].append((x,y))
            x,y = nx,ny # 이동
    
    return answer

 

 

레퍼런스

https://velog.io/@narastro/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%B0%A9%EC%9D%98-%EA%B0%9C%EC%88%98-Python

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

https://dongdongfather.tistory.com/69

[파이썬 기초] 유사 딕셔너리 defaultdict() 활용법

https://yabmoons.tistory.com/606

[ 프로그래머스 방의 개수 (Lv5) ] (C++)