1743번: 음식물 피하기

문제 풀이 아이디어

# 사용해야 하는 알고리즘 = dfs 혹은 bfs (완전탐색)
  : 연결된 음식 1개를 찾기 위해서는 완전 탐색을 통해서
  : 한 음식으로 부터 연결된 모든 음식을 찾아야 합니다.
	:⭐️ 즉 완전탐색을 수행한 횟수를 구하는게 아니라 완전탐색 1번에서 찾은 node의 숫자를 구해야 합니다.

# 문제 풀이 아이디어
  : n + 1 * m + 1 짜리 행렬을 만들고 음식물의 좌표를 표시합니다.
  : 음식이 나오면 완전탐색하고 탐색하는 동안 연결된 음식 갯수를 셉니다.

# 의사코드
  1. n + 1 * m + 1 행렬을 두개 선언해서 하나는 음식물 표시용, 하나는 방문 체크용으로 사용합니다.
  2. 음식물 쓰레기 좌표를 받아서 행렬에 표시합니다.
  3. 표시한 행렬을 이중 반복문으로 모든 좌표를 돌면서
      3-1. 음식을 만나면 dfs를 실시합니다.
          3-1-1. dfs를 실시하면서는 연결된 음식 갯수를 세고
          3-1-2. 연결된 음식은 방문 표시를 합니다.
      3-2. dfs에서 반환된 음식의 갯수를 현재 최댓값과 비교해서 갱신합니다.
  4. 최댓값을 출력합니다.

# 시간복잡도
  : 모든 정점을 방문하고 각 정점마다 동서남북 4번의 반복문 실행하기 때문에 O(4k) = O(k)
  : 이중 반복문 O(n * m)이 있지만 이것은 최대 O(100000)이기 가능합니다.

코드

stack을 사용해서 dfs 구현하는 방법

이 문제는 특이하게 dfs를 수행할 때 방문하는 node의 숫자를 세야합니다. 따라서 stack을 사용하는 방법이 좀 더 직관적으로 이해하기 쉽습니다.

// stack을 활용한 dfs
func dfs(r: Int, c: Int) -> Int {
    var stack = [(Int, Int)]()
    stack.append((r, c))
    check[r][c] = true
    var cnt = 1 //👉 방문한 node의 갯수
    
    while !stack.isEmpty { //👉 stack이 빌 때까지
        let (r, c) = stack.popLast()!
        for i in 0..<4 {
            let nr = r + dr[i]
            let nc = c + dc[i]
            if isValid(r: nr, c: nc) && !check[nr][nc] {
                stack.append((nr, nc))
                cnt += 1 //👉 동서남북 중에 다른 node를 발견하면 1개 추가
                check[nr][nc] = true
            }
        }
    }
    
    return cnt
}

// 현재 좌표가 valid한 좌표인지 알아보는 함수
func isValid(r: Int, c: Int) -> Bool {
    return r > 0 && r <= N && c > 0 && c <= M && matrix[r][c] ? true : false
    // 행렬의 범위 안에 있고 + 해당 위치에 음식물 쓰레기 존재
}

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1], K = input[2]

// 동서남북 방향 이동용 배열
let dr = [1, -1, 0, 0]
let dc = [0, 0, 1, -1]

// 행렬 2개
var matrix = Array(repeating: Array(repeating: false, count: M + 1), count: N + 1)
var check = Array(repeating: Array(repeating: false, count: M + 1), count: N + 1)

// 음식물 쓰레기의 좌표 표시
for _ in 0..<K {
    let coord = readLine()!.split(separator: " ").map { Int(String($0))! }
    matrix[coord[0]][coord[1]] = true
}

// 최종 결과 저장
var result = 0

for r in 1...N {
    for c in 1...M {
        if matrix[r][c] {
            result = max(dfs(r: r, c: c), result) //👉 현재 결과와 dfs에서 구한 값 중에 최대값으로 갱신
        }
    }
}

print(result)

재귀함수를 이용해서 구현한 dfs로 문제를 푸는 방법

직관적으로 이해하기 쉽지않은 방법이지만 dfs를 이용해서 푸는 방법도 있습니다. cnt에 재귀함수의 return 값을 누적해서 콜스택 가장 아래에 있는 (제일 처음 호출한) 함수가 모든 node의 갯수를 세서 리턴하는 것 방식입니다.

쉽게 비유하면 분단장이 자기 분단의 인원을 세서 반장에게 알려주고, 반장이 모두 합쳐서 반의 인원을 전교회장에게 알려주고 전교회장은 모두 합쳐서 전교 인원을 구하는 방식이라고 볼 수 있겠습니다.

//✅ 재귀함수로 구현한 dfs로 완전탐색한 node 갯수 세는 법
func dfs(r: Int, c: Int) -> Int {
    check[r][c] = true
    var cnt = 1 //👉 자기자신 node 갯수
    for i in 0..<4 {
        let nr = r + dr[i]
        let nc = c + dc[i]
        if isValid(r: nr, c: nc) && !check[nr][nc] {
            cnt += dfs(r: nr, c: nc) //👉 현재 cnt에 현재 node에 연결된 node의 갯수만큼 더한다.
        }
    }
    return cnt //👉 최종 갯수 리턴
    //✅ 자기 자신만 연결되어 있다면 1을 리턴
    //✅ 연결된 node가 있다면 그것들 까지 포함해서 리턴
    //⭐️ 최종적으로 콜스택 맨 아래 있는 dfs의 cnt에는 모든 node들의 갯수가 cnt에 추가되게 됨.
}