본문 바로가기
Coding Test/Python

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

by giem 2023. 4. 13.
반응형

프로그래머스 레벨 5 방의 개수를 풀어봤다.

레벨 5중에 정답률이 많이 높은 문제라 도전해 봤는데

실제 난이도는 3~4 정도인 느낌이다.


문제

문제는 위와 같다.

 

예시로 다음 그림이 주어진다.

이렇게 구역이 나눠지면 그 구역의 개수를 세면 된다.


구현

1차적으로 구역이 생기는 경우는 기존에 방문했던 점을 다시 방문했을 때이다.

이것만 생각했다면 실행할 때 테스트케이스는 맞지만 제출을 하면 다 틀리는 상황을 볼 수 있다.

추가로 확인해야 되는 점은 기존에 연결된 간선이 있는지다.

 

따라서 기존에 연결된 간선이 없고 방문했던 노드라면 그때 정답의 개수를 추가해 주면 된다.

 

여기서 대각선의 상황도 추가로 생각해야 한다. 하지만 이 상황은 포인트의 개수를 두배로 늘리며 접근하면 대각선 상황 자체가 사라진다.

 

아래 코드에서 라인 단위 주석으로 설명하겠다.


코드
from collections import defaultdict

#0번부터 8번까지의 방향을 list로 저장
dy = [-1,-1,0,1,1,1,0,-1]
dx = [0,1,1,1,0,-1,-1,-1]

def solution(arrows):
    answer = 0
    #방문한 곳 체크용 set
    visit = set()
    #그린 선 저장용 dict(접근 시간 효율, 중복 제거를 위한 set)
    edge = defaultdict(set)
    
    #초기 좌표 값 & 방문 처리
    x,y=0,0
    visit.add((x,y))
    
    for a in arrows:
    	#대각선 처리를 위해 두 번 반복
        for _ in range(2):
        	#다음 좌표 계산
            nx, ny = x+dx[a], y+dy[a]
            
            #이동할 좌표가 방문했던 점이고 간선이 그려지지 않았을 때
            if (nx,ny) in visit and (x, y) not in edge[(nx,ny)]:
            	#구역 추가
                answer+=1
            #방문한 점이 아닐 때
            elif (nx,ny) not in visit:
            	#방문처리
                visit.add((nx,ny))
            
            #간선 저장
            edge[(nx,ny)].add((x, y))
            edge[(x,y)].add((nx, ny))
            
            #좌표 업데이트
            x,y = nx,ny
        
    return answer

다른 풀이

내가 수학을 좀 더 잘했더라면 아래와 같은 풀이를 할 수 있었을 것이다.

 

오일러 공식을 사용해 모든 선과 라인을 그리고 라인은 중복되므로

면의 개수 = 중복된 선의 개수//2 - 점의 개수 + 1을 해주면 된다.

def solution(arrows):
    answer = 0
    point = set()
    edge = set()
    
    x,y=0,0
    point.add((x,y))
    
    for a in arrows:
        for _ in range(2):
            nx, ny = x+dx[a], y+dy[a]
            
            point.add((nx,ny))
            edge.add((x, y, nx, ny))
            edge.add((nx, ny, x, y))
                
            x,y = nx,ny

    return len(edge)//2-len(point)+1

 

이 풀이는 솔직히 시험을 볼 때는 생각이 날 것 같지 않다...

이런 공식들이 바로바로 생각나는 분들이라면 훨씬 빠르게 해결할 수 있을 문제라고 생각된다.

반응형

댓글