2667. 단지번호붙이기.swift

개요

---

전형적인 탐색 문제였다.

 

문제에서 찾아야 하는 것은 단지의 수와 각 단지에 속하는 집의 수다.

단지의 수를 구하는 것은 간단하다. 방문을 했던 곳은 가지 않고 갈 수 있는 곳만 가면서 확인하면 된다.

 

집의 수를 구하는 법은 여러 방법이 있다. BFS 일 경우 갈 수 있는 Queue를 추가할 때 마다 Count를 센 뒤에 그 값을 출력하면 될 것이며 DFS라면 Depth를 들어갔을 때 마다 Count를 늘려가며 세는 방법이 있을 것 같다.

 

 

풀이

---

이 문제는 dfs 방식으로 접근해보았다. 또한 방문을 해야 하는 곳이 1, 했던 곳이 0으로 단순한 문제이기에 visited 배열을 사용하지 않고 풀 수 있었다. 방문한 곳은 0으로 바꾸어서 방문처리 했다.

 

1. global로 count를 둔 뒤에 depth를 늘릴 때 마다 count에 1 증가

var count = 0

func dfs(_ x: Int, _ y: Int) {
    map[x][y] = 0
    for i in 0..<4 {
        let nx = x + dx[i]
        let ny = y + dy[i]
        
        if nx < 0 || ny < 0 || nx >= n || ny >= n {
            continue
        }
        
        if map[nx][ny] == 1 {
            count += 1
            dfs(nx,ny)
        }
    }
}

첫번째로 통과했던 코드다.

depth를 증가할 때 마다 count를 세도록 하였고 dfs 순회가 종료되면 해당 count를 answer 배열에 추가한 뒤에 count를 0으로 초기화해주었다.

 

2. count를 dfs의 파라미터에 기억해둔 뒤 총합을 return

func dfs(_ x: Int, _ y: Int, _ cnt: Int) -> Int {
    if x < 0 || y < 0 || x >= n || y >= n || map[x][y] == 0 {
        return cnt
    }
    map[x][y] = 0
    
    return dfs(x+1,y,cnt+1) + dfs(x-1,y,0) + dfs(x,y+1,0) + dfs(x,y-1,0)
}

굳이 숫자를 세어줄 필요 없이 방문할 수 있는 경우마다 숫자를 1 씩 증가시켜서 반환했다.

처음에 이 방식에 대해 헷갈렸는데 모든 방향에 대해서 cnt: cnt+1 을 했더니 숫자가 너무 커지게 되었다. count를 중복해서 더해나가서 생겼던 이슈였는데 방문한 케이스 한번에 count가 1개만 증가할 수 있도록 위의 코드처럼 작성을 해서 문제를 해결했다.

어쩌다보니 숏코딩 1등이 되었다..

 

리뷰

---

사실 오답이 나왔던 제출이 정답 직전까지 갔었던 것이었다.

어이없는 실수로 오답이 나왔는데 swift의 정렬 관련된 이슈였다.

for item in (answer.map { String($0) }.sorted()) {
    print(item)
}

처음 배열: [10, 1, 5]

원하는 정답 결과: [1, 5, 10]

코드의 결과: [1, 10, 5]

 

핵심은 정렬하려는 배열이 [String] 였던게 이유였다.

[Int] 배열을 위에처럼 정렬했다면 원했던 결과가 나오겠지만 [String]이었기에 맨 앞에 있는 문자를 기준으로 정렬을 해주는 것 같았다.

 

단순한 실수때문에 답이 왜 안나오지 고민하면서 헤멨던 문제였다.

 

 

Swift 알고리즘 스터디 3주차에 공유했던 내용입니다.

https://bobmongus.notion.site/Week-03-a0ff7025a85145db9d9c0e341bef2dc7