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

https://school.programmers.co.kr/learn/courses/30/lessons/49190?language=swift

프로그래머스

그래프

아래 그림처럼 8가지 방향으로 이동하는 순서가 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 이렇게 배열로 주어지고

이동하면서 선을 그었을 때 생기는 방의 개수를 반환하는 문제

아래의 경우 방의 개수는 3개가 된다.

접근방법

레벨 5에 겁먹고 오랜만에 본 그래프 문제에 겁먹어서 고민 조금 하다가 아래 블로그 참고해서 스위프트로 풀이했다.

방이 생겼음을 확인하는 로직은 '지금 새로 긋는 간선이 이전에 그어진적 없는 선이며, 새로 방문하는 정점은 이미 방문한 적이 있는 정점일 때' 방이 하나 추가된다는 것이다.

따라서 간선의 방문여부와 정점의 방문여부를 전부 저장하면서 이동하면서, 방이 생기는지 여부를 확인하면 되는데

이때 대각선들에 의해 생기는 점에 대해서는 한칸씩 이동해서는 확인하기 어렵기 때문에 두칸씩 이동하면서 선을 그어주어야 한다.

두 칸을 한꺼번에 이동하면 안되고, 한 칸씩 이동하면서 방문여부와 방 생성 여부를 확인해주어야 한다.

아래 블로그는 C++ 풀이고, Swift에서는 map대신에 딕셔너리를 사용하고 key로는 배열을 사용했다.

https://yabmoons.tistory.com/606

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

 

오답노트

오답노트라고 하기도 좀 그렇긴 한데 visit_eg[[cr,cc,nr,nc]] 를 처음에 visit_eg[cr,cc,nr,nc] 로 썼다가 오류났었다.

배열에서 인덱싱하는 것 처럼 visit[1] 겉에 대괄호를 해줘야 key값인거임..! 배열을 키값으로 쓰다보니까 헷갈렸다.

그리고 방문여부 체크할 때, 딕셔너리로 확인하는거기 때문에 방문하지 않았으면 해당 키에 대한 값이 존재하지 않음 -> nil 여부 확인하면 되고, 정점의 경우 방문했다는 걸 확인하는 것이기 때문에 값이 없으면 false로 치환해도 됨

 

소스코드

 

import Foundation

func solution(_ arrows:[Int]) -> Int {
    var answer = 0
    
    let dr:[Int] = [-1,-1,0,1,1,1,0,-1]
    let dc:[Int] = [0,1,1,1,0,-1,-1,-1]
    
    var visit_vt:[[Int]:Bool] = [:] // [0,0]:True 정점 방문여부
    var visit_eg:[[Int]:Bool] = [:] // [0,0, 0,1]:True 간선 방문여부
    
    visit_vt[[0,0]] = true
    var cr:Int = 0
    var cc:Int = 0
    for arrow in arrows {
        for i in 0..<2 { // 대각선 점으로 생기는 공간 계산하기 위해 2칸씩
            let nr:Int = cr + dr[arrow]
            let nc:Int = cc + dc[arrow]
            if (visit_eg[[cr,cc,nr,nc]] == nil) && (visit_vt[[nr,nc]] ?? false) {
                // 방 생김 (새로 생긴 간선이면서 방문하는 점이 이미 지나온 점일 때)
                answer += 1
                visit_eg[[cr,cc,nr,nc]] = true;
                visit_eg[[nr,nc,cr,cc]] = true;
                cr = nr;
                cc = nc;
            } else {
                visit_eg[[cr,cc,nr,nc]] = true;
                visit_eg[[nr,nc,cr,cc]] = true;
                visit_vt[[nr,nc]] = true;
                cr = nr;
                cc = nc;
            }
        }
    }
    
    return answer
}

 

프로그래머스 알고리즘 고득점 Kit 끝!