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

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

BFS로 돌면서 내부를 찾으면 되지 않을까? 싶어서 해보려고 했다. 그런데 arrow의 크기가 10만이라길래 최악의 상황을 가정했을 때 25,000 X 25,000 크기의 2차원 배열을 돌아야하는데 그러면 시간복잡도가 엄청 나올 것 같아서 다른 방법을 찾아보기로 했다.

시도 1 - 같은 점 방문한 횟수 세기

def solution(arrows):
    answer = 0
    start = 0
    
    record = set()
    record.add((0, 0))
    cur = (0, 0)
    
    dy = [1, 1, 0, -1, -1, -1, 0, 1]
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    
    # 엣지 방문기록 저장용, 0번은 0, 0
    visited = [[True] * (len(arrows)+1) for _ in range(len(arrows) + 1)]
    
    for i in range(len(arrows)):
        next = (cur[0] + dy[arrows[i]], cur[1] + dx[arrows[i]])
        
        # 처음 방문한 방향인데 이미 지나간 점에 접근할 때
        if visited[start][i+1] and visited[i+1][start] and next in record:
          answer += 1
        
        visited[start][i+1] = visited[i+1][start] = False
        record.add(next)
        cur = next
        start = i+1
    
    return answer

블로그 검색해서 C++코드를 참고해서 만들었다. map이라는 자료형을 사용하던데 아마 파이썬의 dict와 비슷한 거 인것 같았다. 하지만 dict대신 집합 자료형을 사용해서 점의 방문 기록을 저장했고, visited라는 2차원 배열을 만들어서 간선의 방문기록을 남겼는데 테스트 케이스 전부 실패했고 일부는 시간초과도 났다. 2차원 배열로 방문기록 확인한게 문제인 것 같다.

시도 2 - 딕셔너리

def solution(arrows):
    answer = 0
    
    record = dict()
    record[(0,0)] = True
    cur = (0, 0)
    
    dy = [1, 1, 0, -1, -1, -1, 0, 1]
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    
    # 엣지 방문기록 저장용, 0번은 0, 0
    visited = dict()
    
    for a in arrows:
        next = (cur[0] + dy[a], cur[1] + dx[a])
        
        # 처음 방문한 방향인데 이미 지나간 점에 접근할 때
        if (cur, next) not in visited and next in record:
            answer += 1
        
        visited[(next, cur)] = visited[(cur, next)] = True
        record[next] = True
        cur = next
    
    return answer

딕셔너리 자료형으로 바꿔서 풀었다. 시간초과는 안 떴는데 테스트케이스 2개만 맞고 다 틀렸다. 왜 그런지 찾아보니까 대각선끼리 지나가는 경우에는 가운데 점이 없어서 기록에 남지 않았다. 그래서 점 사이의 거리를 2로 잡고 점이 하나 더 있다고 생각하고 계산이 되도록 코드를 수정했다.

def solution(arrows):
    answer = 0
    
    record = dict()
    record[(0,0)] = True
    cur = (0, 0)
    
    dy = [1, 1, 0, -1, -1, -1, 0, 1]
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    
    # 엣지 방문기록 저장용, 0번은 0, 0
    visited = dict()
    
    for a in arrows:
        for _ in range(2):
            next = (cur[0] + dy[a], cur[1] + dx[a])
            
            # 처음 방문한 방향인데 이미 지나간 점에 접근할 때
            if (cur, next) not in visited and next in record:
                answer += 1
            
            visited[(next, cur)] = visited[(cur, next)] = True
            record[next] = True
            cur = next
    
    return answer