고도고도
🍎🍏
고도고도
전체 방문자
13,424
오늘
31
어제
64
  • 분류 전체보기 (170)
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (61)
      • iOS (28)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Architecture (1)
      • 오늘의 삽질 (7)
      • 에러와의 동침 (1)
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (53)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (10)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

공지사항

인기 글

  • [NCSOFT] 2022 엔씨소프트 썸머 인턴 후기 - 1⋯
    2022.08.10
    [NCSOFT] 2022 엔씨소프트 썸머 인턴 후기 - 1⋯
  • [Flutter] SingleChildScrollView,⋯
    2021.08.18
    [Flutter] SingleChildScrollView,⋯
  • [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
    2022.12.20
    [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
  • [Android] 백그라운드에서 소켓 통신으로 이벤트 수신⋯
    2022.06.08
    [Android] 백그라운드에서 소켓 통신으로 이벤트 수신⋯
  • [iOS / SwiftUI] OnAppear, OnDisa⋯
    2022.12.01
    [iOS / SwiftUI] OnAppear, OnDisa⋯

최근 댓글

  • https://developer.apple.com/docu⋯
    고도고도
  • 게시글 잘 보았습니다. 혹시 주소에서 구를 가지고 오시는⋯
    나그네
  • 혹시 댓글이 안보이는데 .. y2e010924@naver.⋯
    eun
  • 글 솜씨가 뛰어나시네요! 좋은 글 잘 보고 갑니다 다음에도⋯
    alpha-traveler
  • NC......가슴이...웅장해집니다.......🤯
    이상한핑구 🐧

최근 글

  • [Architecture] MVVM + Clean Arch⋯
    2023.01.07
    [Architecture] MVVM + Clean Arch⋯
  • [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
    2022.12.20
    [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
  • [iOS / SwiftUI] OnAppear, OnDisa⋯
    2022.12.01
    [iOS / SwiftUI] OnAppear, OnDisa⋯
  • [에러와의 동침] 22년 11월 4주차
    2022.11.28
    [에러와의 동침] 22년 11월 4주차
  • [iOS / SwiftUI] 스크롤, 무한으로 즐겨요~ (⋯
    2022.11.28
    [iOS / SwiftUI] 스크롤, 무한으로 즐겨요~ (⋯

티스토리

hELLO · Designed By 정상우.
고도고도

🍎🍏

[백트래킹 / Kotlin] BOJ 1987 - 알파벳
✍️ 코테 준비/Back Tracking

[백트래킹 / Kotlin] BOJ 1987 - 알파벳

2022. 4. 10. 11:39

문제

풀이 언어

Kotiln

코드

import java.lang.Integer.max
import java.util.*

var n = 0
var m = 0
var max_value = 0
val dx = listOf(-1, 1, 0, 0)
val dy = listOf(0, 0, -1, 1)
lateinit var board: Array<Array<String>>
lateinit var check: Array<Int>

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()

    board = Array(n) { Array(m) { "" } }
    check = Array(26) { 0 }

    for (i in 0 until n) {
        val s = next().chunked(1)
        for (j in 0 until m) {
            board[i][j] = s[j]
        }
    }

    val index = board[0][0].toCharArray()[0].toInt() - 65
    check[index] = 1

    move(0, 0, 1)

    println(max_value)
}

fun move(x: Int, y: Int, cnt: Int) {
    max_value = max(max_value, cnt)

    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx in 0 until n && ny in 0 until m) {
            val index = board[nx][ny].toCharArray()[0].toInt() - 65
            if (check[index] == 0) {
                check[index] = 1
                move(nx, ny, cnt + 1)
                check[index] = 0
            }
        }
    }
}

풀이 방법

비교적 간단한 백트래킹 문제이다. 방문하지 않은 알파벳 일 경우에 DFS 를 진행하면 된다. 문제를 처음 접했을 때는 방문 여부를 확인하는 2차원 배열과 방문한 알파벳을 저장하는 일차원 배열을 각각 선언해서 진행했었다. 새로 방문하는 좌표가 이미 방문한 알파벳일 수도 있어서 이렇게 따로 선언했었다. 하지만 이럴 필요가 없었다. 방문한 알파벳을 저장하는 일차원 배열만 있어도 충분했다. 이유는 간단하다.

 

- 현재 (2,2)를 방문했고 이곳의 알파벳은 K이다. 일차원 배열에 K의 방문 여부를 저장한다.
- (-1, 0)을 이동해서 (1, 2) 를 방문하려고 한다. 이곳의 알파벳은 D이므로 방문한다.
- 상, 하, 좌, 우를 모두 이동하므로 (1, 0) 을 이동하면 다시 (2, 2) 를 방문한다. 하지만 K는 이미 방문한 알파벳이므로 따라서 방문하지 않는다.


이처럼 방문 여부를 확인하는 일차원 배열만 선언해도 충분했다.

 

1. 입력 값을 2차원 배열에 저장

    for (i in 0 until n) {
        val s = next().chunked(1)
        for (j in 0 until m) {
            board[i][j] = s[j]
        }
    }

 

2. (0,0) 을 방문하고 DFS 를 진행

    val index = board[0][0].toCharArray()[0].toInt() - 65
    check[index] = 1

    move(0, 0, 1)

 

3. 상, 하, 좌, 우 를 탐색하며 방문하지 않은 알파벳일 경우 DFS 를 진행

fun move(x: Int, y: Int, cnt: Int) {
    max_value = max(max_value, cnt)

    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx in 0 until n && ny in 0 until m) {
            val index = board[nx][ny].toCharArray()[0].toInt() - 65
            if (check[index] == 0) {
                check[index] = 1
                move(nx, ny, cnt + 1)
                check[index] = 0
            }
        }
    }
}

결과

저작자표시 비영리 변경금지

'✍️ 코테 준비 > Back Tracking' 카테고리의 다른 글

[백트래킹 / Kotlin] BOJ 14889 - 스타트와 링크  (0) 2022.04.10
[백트래킹 / Kotlin] BOJ 1759 - 암호 만들기  (0) 2022.04.10
[백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기  (0) 2022.03.31
[백트래킹 / Kotlin] BOJ 2580 - 스도쿠  (0) 2022.03.30
[백트래킹 / Kotlin] BOJ 9663 - N Queen  (0) 2022.03.29
    '✍️ 코테 준비/Back Tracking' 카테고리의 다른 글
    • [백트래킹 / Kotlin] BOJ 14889 - 스타트와 링크
    • [백트래킹 / Kotlin] BOJ 1759 - 암호 만들기
    • [백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기
    • [백트래킹 / Kotlin] BOJ 2580 - 스도쿠
    고도고도
    고도고도
    iOS 꿀잼
    댓글쓰기
    [백트래킹 / Kotlin] BOJ 1759 - 암호 만들기
    다음 글
    [백트래킹 / Kotlin] BOJ 1759 - 암호 만들기
    [백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기
    이전 글
    [백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기

    티스토리툴바