[백준] (Swift) 2210번 - 숫자판 점프 (DFS, 재귀)

⚫️ 문제

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

2210번: 숫자판 점프

 

⚫️ 나의 풀이

문제를 보자마자 DFS임을 직감했다. 시작점으로부터 가장 깊은 depth까지 파고들고, 그 부분에서 6글자가 되면 딱 dfs함수를 멈춰주면 되는 부분이므로 dfs재귀를 사용하면 되는구나! 생각했다. (확실히 개념을 탄탄히 하고 하니까 보이긴 보이는 고만, 뿌--듯)

그래서 내가 생각한 dfs의 구조는 다음과 같다.

그리고 dfs는 6글자가 되면 바로 return 해주고 탈출하기 때문에, 시작점을 전부 바꿔서 전부다 탐색해주어야한다! 그래서 dfs를 실제로 실행하는 부분은 for문으로 시작점을 전부 넣어주어야한다. 이것을 코드로 그대로 구현해주면 아래와 같다.

⚫️ 정답코드

한 번 틀린 이유는,,, count를 출력해야하는데 array 그대로 전부 출력해줬다 ,, 문제를 잘보자 후후 

import Foundation

var matrix = [[Int]]()
for _ in 0..<5 {
    matrix.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

var answerList = [String]()

private func dfs(x: Int, y: Int, number: String) {
    var number = number
    number += String(matrix[x][y])

    if number.count == 6 {
        answerList.append(number)
        return
    }

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

        if nx < 0 || nx >= 5 || ny < 0 || ny >= 5 {
            continue
        }

        dfs(x: nx, y: ny, number: number)
    }
}

for i in 0..<5 {
    for j in 0..<5 {
        dfs(x: i, y: j, number: "")
    }
}

print(Set(answerList).count)

 

---

 

💬 그냥,, 주저리주저리

스터디친구들과 DFS/BFS 알고리즘 문제풀이를 일주일동안 시작했다. 그냥 무턱대고 문제를 풀려고 했지만, 이번에 풀 문제들은 전부 백준 실버1 이상 수준이었고, 그대로 풀면 또 인터넷을 마구 참고하면서 풀게 뻔했다... dfs/bfs가 문제 유형만 익히면 완전 암기문제라고 그러는데, 난 왤케 어렵지? 아직 개념을 파악하지 못해서 인것 같아서, 다시 공부를 했다. 그 공부 내용은 아래 참고! 

https://github.com/HotCodeBreakers/CodingTest/discussions/25

[개념정리] DFS+BFS (혹시,,, 문제풀이 전에 이코테 책을 보시나요!?) · Discussion #25 · HotCodeBreakers/Codi

이것이 코딩테스트다 라는 책을 기준으로 공부를 하기로 했는데, 우리는 그냥 범위만 맞춰풀고 책을 위주로 문제를 가져가지 않는다! 파이썬이 아니기도하고, 책에 있지만 인터넷에는 없는 문제가 많기 때문...

그래서 그냥 무턱대고 개념 공부를 하지 않고 지나갔는데, 확실히,,,, 처음부터 차근차근 개념을 익히고 유형을 파악하고 문제를 풀어보니 더 쉽게 풀리는 기분이다. 앞으로 개념공부를 소홀히 하지 말아야겠다아아! 화이팅