[백준 1743] swift 음식물 피하기: DFS

문제 설명

https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

간단하게 상하좌우로 움직일 수 있고 그 쓰레기의 크기를 구하는 문제이다.

 

 

문제 풀이

DFS로 풀어봤다. 2차원배열로 map과 visited 배열을 만들고 쓰레기면 1, 아니면 0으로 표시했다.

 

1000
0110
1100

위의 예제에서 이렇게..


그리고 for문을 돌면서 쓰레기이고 방문하지 않은 경우에 DFS를 돌려주며 count를 +1 해주었다.

DFS가 끝나고 나올 때는 다시 count를 0으로 초기화해주고 count가 제일 큰 값을 저장해주면 된다.

 

 

코드

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let height = input[0], width = input[1], k = input[2]
var map = Array(repeating: Array(repeating: 0, count: width), count: height) // 쓰레기 있으면 1 없으면 0
var visited = Array(repeating: Array(repeating: false, count: width), count: height)
let dy = [0, 0, -1, 1] // 상하좌우
let dx = [-1, 1, 0, 0]
var answer = Int.min
var count = 0

for _ in 0..<k {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let h = input[0]-1, w = input[1]-1
    map[h][w] = 1 // 쓰레기는 1
}

func DFS(_ x: Int, _ y: Int) {
    visited[y][x] = true // 방문 처리
    count += 1 // 쓰레기 개수 추가
    
    for i in 0..<4 {
        let nx = dx[i] + x
        let ny = dy[i] + y
        // map의 범위에 있고 방문하지 않았고 쓰레기인 경우에만 DFS 돌림
        if nx >= 0 && nx < width && ny >= 0 && ny < height && !visited[ny][nx] && map[ny][nx] == 1 {
            DFS(nx, ny)
        }
    }
    
}

for y in 0..<height {
    for x in 0..<width {
        if map[y][x] == 1 && !visited[y][x] { // 쓰레기이고 방문하지 않은 경우만 DFS 돌림
            count = 0
            DFS(x, y)
            answer = max(answer, count) // DFS 다 돌리고 나온 쓰레기 개수의 max값 저장
        }
        
    }
}

print(answer)

 

후기

사실 대표적인 탐색 문제인데.. 오랜만에 DFS 문제를 풀어서 많이 헤맸다..ㅠㅠ

문제를 잘못 생각해서 depth로 풀다가 다시 생각해보니 완전 잘못된 풀이었다....ㅎㅎ

func DFS(_ x: Int, _ y: Int, _ depth: Int) {
    answer = max(answer, depth) // DFS의 깊이 계산
    visited[y][x] = true // 방문 처리

    for i in 0..<4 {
        let nx = dx[i] + x
        let ny = dy[i] + y
        // map의 범위에 있고 방문하지 않았고 쓰레기인 경우에만 DFS 돌림
        if nx >= 0 && nx < width && ny >= 0 && ny < height && !visited[ny][nx] && map[ny][nx] == 1 {
            DFS(nx, ny, depth+1)
        }
    }

}

이런 식으로 DFS의 깊이를 더해갔는데 문제는 깊이가 아니라 DFS를 도는 개수를 구하는 것이었다,,😅
count로 개수를 더해가는 걸로 수정했더니 바로 풀림