[Android, 내일배움캠프] 공부일지(2024-06-24)

오늘 공부한 내용 정리(2024년 6월 24일)

 

 

코드카타 문제풀이

단지 번호 붙이기(Silver 1, 2667번)

문제 내용

 

문제 풀이 방법

1이 집이 있는 곳, 0이 집이 없는 곳일 때, 아파트 단지의  개수와 각 단지 내 집의 개수를 오름차순으로 정렬해 출력.

이 문제에서 아파트 단지의 정의는 1이 2개 이상 연결되어 있지 않고 1이 각각 따로 떨어져 있어도 개별의 단지로 인식한다.

 

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader

private val dx = listOf(-1,1,0,0)
private val dy = listOf(0,0,-1,1)

private var graph = arrayOf<MutableList<Int>>()
private var visited = arrayOf<Array<Boolean>>()
private var apartment = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    val apartments = mutableListOf<Int>()
    var apartmentComplex = 0

    graph = Array(size) { mutableListOf() }
    visited = Array(size) { Array(size) { false } }

    for (i in 0 until size) {
        val list = readLine().map { it.digitToInt() }
        graph[i].addAll(list)
    }

    for (i in graph.indices) {
        for (j in graph[i].indices) {
            if (graph[i][j] == 1 && !visited[i][j]) {
                apartment = 1
                visited[i][j] = true
                dfs(i, j)
                apartmentComplex++
                apartments.add(apartment)
            }
        }
    }

    apartments.sort()
    println(apartmentComplex)
    println(apartments.joinToString("\n"))
}

private fun dfs(x: Int, y: Int) {
    for (i in dx.indices) {
        val nx = x +dx[i]
        val ny = y +dy[i]

        if (nx in graph.indices && ny in graph.indices) {
            if (graph[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true
                apartment++
                dfs(nx, ny)
            }
        }
    }
}

 

풀이 과정

상하좌우의 데이터를 확인할 dx, dy를 생성한다.

아파트 구조를 저장할 graph와 한 번 방문한 아파트를 다시 방문하지 않기 위한 visited를 생성한다.

아파트 단지 당 아파트가 몇 개가 있을지 셀 변수(apartment)도 생성한다. graph와 visited를 입력받은 size로 설정해 준다. graph에 입력받은 값을 넣어준다.

 

그래프를 반복문으로 모두 체크한다.

그래프의 데이터가 1이고 visited가 false인 경우는 새로운 아파트 단지가 있다는 뜻이다.

apartment를 1로 초기화하고(위 조건을 만족한 아파트이므로 1로 초기화), 그래프를 탐색한다.

 

탐색 이후 아파트 단지 개수를 세는 변수(apartmentComplex)에 1을 더해준다.

그래프 탐색 함수(dfs)에는 이전에 생성한 dx, dy를 사용해 기준 데이터에 상하좌우의 값을 모두 확인해서 탐색하는 데이터가 1이거나 visited가 false일 때만 apartment를 1씩 증가시킨다.

그리고 재귀 호출을 통해 기준 데이터를 변경해서 다시 탐색한다.

 

 

문제 해결 과정

위 코드를 짜고 나서 채점을 해보니 3%에서 틀렸다고 나왔다. 다른 사람들도 많이 3%에서 틀려서 질문 게시판에 글을 많이 올렸었는데 나한테는 모두 해당되지 않았다. 그래서 문제를 다시 읽어보니까 출력을 단지의 개수와 각 단지의 아파트의 개수를 오름차순으로 출력하는 문제였다. 오름차순으로 정렬해 다시 문제를 채점했더니 맞았다.

 

 

영역 구하기(Silver 1, 2583번)

문제 내용

t

 

문제 풀이 방법

영역의 size(M, N)이 주어지고 막힌 영역의 개수 K가 주어질 때, 막힌 영역의 시작 좌표(x, y)와 끝 좌표(x2, y2)가 K번 주어질 때, 영역의 개수와 각 영역의 넓이를 오름차순으로 정렬해서 출력한다.

 

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader

private var graph = arrayOf<Array<Int>>()
private var visited = arrayOf<Array<Boolean>>()

private val dx = listOf(-1,1,0,0)
private val dy = listOf(0,0,-1,1)

var zoneCnt = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (width, height, case) = readLine().split(" ").map { it.toInt() }

    graph = Array(width) { Array(height) { 1 } }
    visited = Array(width) { Array(height) { false } }

    val zones = mutableListOf<Int>()
    for (c in 0 until case) {
        val (startP1, startP2, endP1, endP2) = readLine().split(" ").map { it.toInt() }

        for (w in startP2 ..< endP2) {
            for (h in startP1 ..< endP1) {
                graph[w][h] = 0
            }
        }
    }

    for (i in 0 until width) {
        for (j in 0 until height) {
            if (graph[i][j] == 1 && !visited[i][j]) {
                zoneCnt = 1
                visited[i][j] = true
                find(i, j)
                zones.add(zoneCnt)
            }
        }
    }

    println(zones.size)
    zones.sort()
    println(zones.joinToString(" "))
}

private fun find(x: Int, y: Int) {
    for (i in dx.indices) {
        val nx = x +dx[i]
        val ny = y +dy[i]

        if (nx in graph.indices && ny in graph[x].indices) {
            if (graph[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true
                zoneCnt++
                find(nx, ny)
            }
        }
    }
}

 

풀이 과정

상하좌우를 탐색할 dx, dy를 생성한다.

영역의 개수를 출력할 zoneCnt를 생성한다.

입력받은 width, height의  길이를 가지는 이중리스트 graph와 visited를 초기화한다.

각 영역의 넓이를 구할 zones를 생성한다.

 

case번 반복하면서 startP와 endP 좌표를 입력받고 반복을 통해 해당 좌표에 해당하는 영역의 모든 숫자를 0으로 변경한다(막힌 영역).

 

막힌 영역을 적용하고 나면 이중 for문을 돌면서 graph를 탐색한다.

탐색 중인 데이터가 1이고 visited가 false이면 새로운 영역을 발견했다는 뜻이기 때문에 zoneCnt를 1로 변경 겸 초기화를 해주고 find 함수를 수행한다.

 

find 함수에서는 시작점 데이터(1 임)의 상하좌우를 탐색해 1이 더 없거나 1이 있어도 visited가 true일 때까지 재귀를 돌면서 탐색한다(탐색하면서 zoneCnt도 1씩 늘려준다).

 

find 함수 종료 후 최종 zoneCnt를 zones에 넣어 준다.출력은 zones의 size와 zones를 sort 한 데이터를 순서대로 출력한다.

 

 

문제 해결 과정

위에 작성한 단지 번호 붙이기와 흡사한 유형의 문제이다.

그래서 큰 어려움은 없었다.

 

 

개인 공부

매내처 알고리즘

공부 내용 간단 정리

블로그 내용

https://rkdrkd-history.tistory.com/131

[알고리즘] 매내처 알고리즘(Manacher) 개념

 

 

---

 

오늘 공부 내용 정리 및 회고

오늘은 그래프 탐색 문제 풀이와 매내처 알고리즘 공부를 하루 종일 했다.

그래프 탐색 문제는 아직까지도 어렵다. 빨리 적응을 해서 골드 문제를 풀어보고 싶다.

매내처 알고리즘은 생소한 알고리즘이기도 하고 원리는 이해했는데 코드로 짜는 것이 좀 막막하다. 시간을 들여서 공부해 봐야겠다.

항상 월요일만 되면 매우 피곤하다. 월요병인가?