[swift] 백준 - 1012번: 유기농 배추

1012번: 유기농 배추

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

나의 풀이

let input = Int(readLine()!)!
var farm = [[Bool]]() // 1
var visited = [[Bool]]()
let dirX = [1, -1, 0, 0]
let dirY = [0, 0, 1, -1]

func dfs(_ y: Int, _ x: Int) {
    visited[y][x] = true
    for i in 0...3 {
        let newX = x + dirX[i]
        let newY = y + dirY[i]
        if farm[newY][newX] && !visited[newY][newX] {
            dfs(newY, newX)
        }
    }
}

for _ in 0..<input {
    let WHK = readLine()!.split(separator: " ").map { Int($0)! }
    farm = Array(repeating: Array(repeating: false, count: WHK[0]+2), count: WHK[1]+2) // 2
    visited = farm
    var result = 0

    for _ in 0..<WHK[2] {
        let bug = readLine()!.split(separator: " ").map { Int($0)! }
        farm[bug[1]+1][bug[0]+1] = true // 3
    }

    for i in 1...WHK[1] {
        for j in 1...WHK[0] {
            if farm[i][j] && !visited[i][j] {
                dfs(i,j)
                result += 1
            }
        }
    }
    print(result)
}

 

DFS(깊이우선탐색)를 사용하여 푼 첫 번째 풀이다.

DFS입문으로 아주 좋은 기본문제다.

 

편하게 되짚어 보기위해 주석을 달아놨다.

주석 순서로 설명해볼려고 한다.

 

// 1

현재 풀이는 정석적인 풀이라 할 수 있는데

기본배열(farm)과 방문배열(visited)를 나눠서 푸는 걸 말한다.

farm은 우리가 탐색해야 하는 부분을 저장하고 있고

visited는 방문한 곳을 저장하고 있다.

 

이 방법 말고 기본배열에서 방문하는 로직을 합쳐 문제를 풀 수도 있다.

 

하지만 첫문제인만큼 정석으로 기본배열과, 방문배열 두 개를 초기화시켰다.

 

 

// 2

배열 x 왼쪽, 오른쪽에 빈 공간을 두었고

y 위쪽, 아래쪽에도 빈 공간을 두었다.

 

탐색을 할 때 인덱스가 넘치지 않게 하기 위함!

	0	0	0	0
	0	0	0	0
	0	0	0	0
	0	0	0	0

인덱스가 0일 때 왼쪽으로 간다면 에러가 나겠지만

빈공간을 두었기 때문에 첫 인덱스가 1이다.

따라서 왼쪽으로 이동한다고 해도 에러가 나지 않는다.

 

 

// 3

빈공간을 생각해서 +1씩 더해 할당한다.

 

---