[백준] (Swift) 1743번 - 음식물 피하기 (DFS)

💬 잡담부터 start

어제 친구와 깊은 dfs 와 bfs에 대해서 고찰해본 뒤, 첫 문제풀이다. dfs/bfs관련 문제를 그래도 ... 50개정도... 는 풀었나..? 그 이상인가.. 어쨌든 그정도 푸니까 문제 유형은 대애애충 파악했고.. 이제 이게 정말 BFS인지 DFS인지 머리를 굴리기 시작했다. (원래였으면 대충 그냐 완탐=bfs지! 라는 바보같은 소리를 적어내려가고 있겠지. 땡큐,,,마이프랜드) 아래는 내가 문제를 풀면서 잘못 짚고 넘어갔던 BFS와 DFS에 대한 개념을 살펴볼 수 있다.

https://didu-story.tistory.com/422

[알고리즘] 2023.02.25 DFS와 BFS에 대한 고찰

이러한 시간을 갖고 문제를 접근하니 DFS가 뭔지, BFS가 뭔지 정확하게 파악할 수 있었다. 역시, 개념만 보고 무턱대고 아무거나 구현했던 불과 1주일전의 나와는 조금 달라졌다. 뿌--듯,, 하달까 ^__ ^ 뭐어쨌든,, 문제풀이 ㄱ

⚫️ 문제

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

1743번: 음식물 피하기

⚫️ 나의 풀이

이문제는 DFS를 이용해서 풀었다. 내가 처음에 생각한 흐름은 다음과 같다.

dfs를 이용해서 연결된 노드중 제일 깊은곳까지 탐색 하고 cnt를 갱신해주는 방식이다.
여기에는 visited 변수도 따로 만들어놨고, cnt를 answer이라는 배열에 넣어 그중에서 max값을 찾는 것으로 그림을 그렸지만, 실제 코드를작성할때는 흐름은 같지만 조금 변형되게 코드를 구현했다.

굳이 visited 배열을 따로 만들지 않고, 애초에 입력되는 arr를 사용했다. 입력을 받을때 음쓰가 있는 곳에는 -1을 넣어주었고, dfs를 돌리면서 음쓰의 갯수를 세어줄때 +1씩해서 1, 2,3,4, 이런식으로 수를 채워주었다. 

결과는 이렇게 된다. 음쓰가 시작할떄는 1로 시작한다. arr[0][0]자리에 있는 음쓰는 덩그러니 놓여있는 한개짜리 음쓰기 때문에 1로만 입력되었고, 뒤에 보면 4개짜리가 연결된 음쓰에는 1,2,3,4 순서대로 입력되어있다. 여기서 가장 큰 max 4를 출력해주면 된다.

⚫️ 정답코드

import Foundation

let nmk = readLine()!.split(separator: " ").map { Int($0)! }
var arr = Array(repeating: Array(repeating: 0, count: nmk[1]), count: nmk[0])
var answer = -9999
var cnt = 0

// MARK: - 방향키 상하좌우
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

// MARK: - 음쓰 있으면 -1, 없으면 0
for _ in 0..<nmk[2] {
    let rc = readLine()!.split(separator: " ").map{ Int($0)! }
    arr[rc[0]-1][rc[1]-1] = -1
}

private func dfs(x: Int, y: Int) {
    cnt += 1
    arr[x][y] = cnt

    for i in 0..<4 {
        let nx = x + dx[i]
        let ny = y + dy[i]

        if nx < 0 || ny < 0 || nx >= nmk[0] || ny >= nmk[1] {
            continue
        }

        if arr[nx][ny] == -1 {
            arr[nx][ny] = cnt
            dfs(x: nx, y: ny)
        }
    }
}

for i in 0..<nmk[0] {
    for j in 0..<nmk[1] {
        if arr[i][j] == -1 {
            cnt = 0
            dfs(x: i, y: j)
        }

        if answer < arr[i][j] {
            answer = arr[i][j]
        }
    }
}

print(answer)

 

점점 개념이 잡혀가면서 풀리는 문제들을 보니까 기분이 좋고 재밌다! 물론 이 문제는 DFS에서 가장 기초가 되는 문제이기에.. 아직 재밌어하고 기쁘긴 이르지만,,, 그래도 기분이 좋은걸 어떡해