개발해요

https://programmers.co.kr/learn/courses/30/lessons/87694

처음에 어떻게 풀어야 할지 감이 안 와서 고민해보다가 다른 분들의 힌트를 봤다. 생활 패턴 고친다고 밤을 새워서 그런지(핑계 맞음ㅎㅎ) 봐도 무슨 말인지 모르겠더라. 짐 싸서 집 가는 길에 백준에서 비슷한 문제를 풀었던 기억이 갑자기 떠올랐다ㅋㅋ. 신기하게도 샤워하거나 산책하면 아이디어가 잘 떠오르는데, 이유는 뭘까?

아무튼 DFS나 BFS로 풀 수 있다는 것까진 알았는데, 이번엔 어떻게 테두리만 표시할지 떠오르지 않았다. 결국 다른 분의 풀이를 봤는데, 대단한 사고력이 필요하진 않았고 오히려 방법이 단순했다. 최근에 코테 실력이 많이 는 것 같아서 "나 이제 코테 좀 치나?ㅋㅋ" 싶었는데, 반성했다.

결론적으론 나에게 어려운 문제였다.

요약

1. 좌표 및 사각형 영역을 2배로 늘린다
2. 그래프에 모든 사각형의 테두리를 표시한다. (1 vs 0 or true vs false)
3. 사각형의 테두리를 제외한 안쪽 영역(너비)을 빈공간으로 표시한다.
4. 테두리 전체 길이(S)와 시작점에서 도착점(src- dst)까지의 길이를 각각 구한다.
5. 정답: min(S - (src - dst), src - dst)

풀이

1. DFS/BFS로 해결할 수 있다

그래프를 점과 빈공간으로 표시할 때, 테두리만을 나타낼 수 있으면 시작점에서 도착점까지 얼마나 이동했는지를 DFS/BFS로 알 수 있다.

2. 좌표를 늘린다!

테두리를 따라가려면 인접한 1을 탐색하면 된다. 하지만 테두리간 거리가 1이면 위와 같은 상황에서 테두리를 잘못 따라갈 수 있다. 따라서, 좌표를 모두 2배로 늘려서 위와 같은 문제를 예방한다.

3. 어떻게 바깥의 테두리만 표시할 수 있을까?

1. 우선 모든 사각형의 테두리를 표시한다.

2. 테두리 안쪽 영역을 빈공간으로 표시한다. 그럼 사각형에 포함되어 있던 테두리가 제거된다.

코드

class Solution {
    static final int SIZE = 101;
    static boolean[][] board = new boolean[SIZE][SIZE]; // true: 점 

    int[] dR = new int[]{-1, 1, 0, 0};
    int[] dC = new int[]{0, 0, -1, 1};

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        // 좌표 2배로 늘리기
        int srcRow = characterY * 2;
        int srcCol = characterX * 2;
        int dstRow = itemY * 2;
        int dstCol = itemX * 2;

        markRect(rectangle); // 그래프에 사각형 테두리만 표시
        
        // + 1: 마지막 위치에서 시작점으로 돌아온 거리
        int totalDistance = findDistance(srcRow, srcCol, srcRow, srcCol, new boolean[SIZE][SIZE], 0) + 1; 
        int distance = findDistance(srcRow, srcCol, dstRow, dstCol, new boolean[SIZE][SIZE], 0);

        return Math.min(distance, totalDistance - distance) / 2;
    }

    private void markRect(int[][] rectangles) {
        for (int[] rect: rectangles) {
            int firstRow = 2* rect[1];
            int firstCol = 2* rect[0];
            int secondRow = 2* rect[3];
            int secondCol = 2* rect[2];

            markEdge(firstRow, firstCol, secondRow, secondCol);
        }

        for (int[] rect: rectangles) {
            int firstRow = 2* rect[1];
            int firstCol = 2* rect[0];
            int secondRow = 2* rect[3];
            int secondCol = 2* rect[2];

            markSpace(firstRow, firstCol, secondRow, secondCol);
        }
    }

    // 그래프에 테두리 모두 표시
    private void markEdge(int firstRow, int firstCol, int secondRow, int secondCol) {
        for(int row = firstRow; row <= secondRow; row++) {
            board[row][firstCol] = true;
        }
        for(int col = firstCol + 1; col <= secondCol; col++) {
            board[secondRow][col] = true;
        }
        for(int row = secondRow - 1; row >= firstRow; row--) {
            board[row][secondCol] = true;
        }
        for (int col = secondCol - 1; col > firstCol; col--) {
            board[firstRow][col] = true;
        }
    }

    // 테두리를 제외한 사각형 너비 영역을 모두 빈공간으로 표시한다
    private void markSpace(int firstRow, int firstCol, int secondRow, int secondCol) {
        for (int row = firstRow + 1; row < secondRow; row++) {
            for (int col = firstCol + 1; col < secondCol; col++) {
                board[row][col] = false;
            }
        }
    }

    // DFS
    private int findDistance(int row, int col, final int dstRow, final int dstCol, final boolean[][] visited, int count) {
        if (count > 0 && row == dstRow && col == dstCol) {
            return count;
        }

        visited[row][col] = true;

        for (int i = 0; i < 4; i++) {
            int newRow = row + dR[i];
            int newCol = col + dC[i];

            if (newRow >= 0 && newRow < SIZE && newCol >= 0 && newCol < SIZE && board[newRow][newCol] && !visited[newRow][newCol]) {
                return findDistance(newRow, newCol, dstRow, dstCol, visited, count+1);
            }
        }

        return count;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/49191

안녕하세요, 이륙사입니다.

오늘 프로그래머스에서 순위라는 문제를 풀어봤는데 어렵다는 생각이 들었습니다. 그래서 제 힘으로 풀진 못하고 다른 분들 풀이를 찾아봤는데, 대부분 플로이드 와샬을 사용해서 푸셨더라구요. 그런데 왜 꼭 그래야 하는지가 명쾌하게 나와있지 않아서 좀 답답했습니다. 그러던 중 DFS만을 사용해서 푸신 분이 계셔서 해당 풀이를 공부하고 공유해보려고 합니다. 

정리

1. 문제를 그래프로 표현할 수 있다: 선수(노드), 경기(엣지) 승패(엣지 방향)
2. 이길 수 있는 선수 + 지는 선수의 합이 n-1인 선수는 순위가 확정된 것이다.
3. 각 선수마다 누구에게 이기고 지는지를 모두 확인한다. 즉, (a > b), (b > c) -> (a > c) 처럼 건너 관계까지 모두 확인한다. --> DFS를 사용한다
4. a > b를 확인할 때, 반대로 b < a 라는 정보도 확인할 수 있다. 즉, 각 선수마다 이기는 정보에 대한 DFS 탐색을 진행하면 지는 관계까지 모두 확인할 수 있다. --> 그러므로 각 선수를 시작노드로 각각 DFS를 진행한다

풀이

두 선수가 이기고 지는 관계를 그래프의 노드, 엣지, 엣지방향으로 나타낼 수 있습니다.

엣지 방향을 어떻게 하든 상관 없지만 저는 노드에서 나가는 방향이 이기는 것, 들어오는 방향이 지는 것으로 표현했습니다. 대회에서 이기면 경기를 더 치룰 수 있지만 지면 짐싸서 집으로 돌아와야 하기 때문이죠. 물론 문제에선 그렇지 않지만요!ㅋㅋ

그래프

근데 왜 그래프로 생각해야 할까요? '그냥 그렇게 하는게 자연스러우니까, 당연하니까, 문제 분류가 그래프니까' 라고 생각할 수도 있지만, 나름의 이유를 부여할 수도 있습니다.

이를 단순 리스트로 표현하면 [1, 3], [3, 2]가 됩니다. 그리고 이 정보만으론 순위를 판별할 수 없습니다. 그냥 '1 > 3, 3 > 2 이니까 당연히 1  > 2고, 1 > 3 > 2가 되지'라고 생각할 수 있지만, 사실 이것이 그래프적으로 사고한 겁니다. (1 -> 3), (3 -> 2)의 과정을 거친것이죠. 단순 배열처럼 생각한다면 그 너머에 있는 관계까지 파악하는 것이 힘듭니다.

키 포인트

그리고 이것이 문제의 핵심 키포인트입니다. 건너건너 연결된 관계까지 모두 확인해야만 경기 결과 속에 숨어있는 모든 순위 관계를 파악할 수 있습니다. 그리고 이 과정에서 DFS가 사용됩니다.내가 이기는 상대가 이기는 상대가 이기는... 을 모두 파악해야 하기 때문입니다.

순위 확정 판별 조건

순위가 확정됐음은 어떻게 판별할 수 있을까요? 우선 모든 관계를 파악합니다. 그리고 n명의 선수들이 있을 때, 특정 선수가 이기는 선수 + 지는 선수 = (n-1)명이라면, 그 선수는 순위가 확정됐다고 판단할 수 있습니다. 그래프에서는, 한 node에서 들어오거나 나가는 edge의 수가 n-1인 node를 의미합니다 (건너건너 포함).

// 순위를 알 수 있는 선수의 수를 센다
for (i in 1..n){
    if (edgeCount[i] == n-1) answer++
}

예를 들어, 1번이 3번을 이기고, 3번이 2번에게 이기면 3번의 입장만 고려했을 때, 3명 중 2명과의 관계를 알고 있으므로 순위가 확정된 것입니다.

DFS

DFS를 사용하여 각 선수마다 내가 이길 수 있는 모든 선수와 내가 지는 모든 선수를 알아냅니다. 그리고 몇 명인지만 알면 되기 때문에 문제는 더 간단해집니다.

각 노드를 시작 노드로 해서 이길 수 있는 모든 선수를 확인합니다. 그리고 그 과정에서 반대로 지는 선수는 그 시작 노드에게 진다는 체크를 해줍니다. 즉, 이기는 노드들에 대한 방문만을 통해 지는 정보까지 모두 알 수 있게 됩니다.

/*
    * src: 이기는 선수 current: 지는 선수, loser: current에게 지는 선수
    * src가 이길 수 있는 모든 선수를 DFS로 확인한다.
    * 이 과정에서 반대로 current들은 src에게 진다는 정보도 알 수 있다.
    */
    private fun countEdgesOf(src: Int, current: Int) {
        for (loser in winList[current]) {
            if (visited[src][loser]) continue
            
            visited[src][loser] = true
            
            // 관계가 n-1개인지만 확인하면 되기 때문에
            // 이기고 지는 경우 상관없이 관계 개수를 카운팅한다.
            count[src]++   // src가 loser를 이긴다
            count[loser]++ // loser는 src에게 진다
            countEdgesOf(src, loser) // 건너 관계를 확인한다.
        }
    }

위의 예를 다시 가져와 보겠습니다. [1, 3], [3, 2]가 입력으로 들어오고, 1에 대해 DFS를 시작합니다.

depth1) 1 -> 3

- 1이 3을 이긴다. (edgeCount[1]++;)

- 3이 1한테 진다. (edgeCount[3]++;)

1에서 3을 방문할 때 1에 대한 정보만이 아닌 3에 대한 정보도 확인할 수 있습니다. 또한, 엣지의 개수만 센다는 것에 주목해주세요. 실제로 필요한건 관계의 개수이기 때문입니다.

depth2) (1 ->) 3 -> 2

앞에 (1 ->)가 있습니다. 1에서부터 시작했다는 의미입니다.

1이 2를 이긴다. (edgeCount[1]++;)

2가 1한테 진다. (edgeCount[2]++;)

정답

이것을 모든 노드에 대해 실행한 후, edgeCount[i] == n-1인 개수를 세면 그것이 답이 됩니다.

코드

class Solution {
    private lateinit var edgeCount: IntArray // 들어오거나 나가는 edge 개수
    private lateinit var visited: Array<BooleanArray> // visited[src][dst]
    private lateinit var winList: Array<MutableList<Int>> // [node]가 이긴 선수들
    
    fun solution(n: Int, results: Array<IntArray>): Int {
        var answer = 0
        edgeCount = IntArray(n+1)
        visited = Array(n+1){
            BooleanArray(n+1)
        }
        winList = Array(n+1) {
            mutableListOf<Int>()
        }
        
        results.forEach {
            val winner = it[0]
            val loser = it[1]
            
            winList[winner].add(loser)
        }
        
        // 모든 관계를 확인한다
        for (i in 1..n) {
            countEdgesOf(i, i)
        }
        
        // 순위를 알 수 있는 선수를 센다
        for (i in 1..n){
        	if (edgeCount[i] == n-1) answer++
        }
        
        return answer
    }
    
    /*
    * src: 이기는 선수 current: 지는 선수, loser: current에게 지는 선수
    * src가 이길 수 있는 모든 선수를 DFS로 확인한다.
    * 이 과정에서 반대로 current들은 src에게 진다는 정보도 알 수 있다.
    */
    private fun countEdgesOf(src: Int, current: Int) {
        for (loser in winList[current]) {
            if (visited[src][loser]) continue
            
            visited[src][loser] = true
            
            // 관계가 n-1개인지만 확인하면 되기 때문에
            // 이기고 지는 경우 상관없이 관계 개수를 카운팅한다.
            edgeCount[src]++   // src가 loser를 이긴다
            edgeCount[loser]++ // loser는 src에게 진다
            countEdgesOf(src, loser) // 건너 관계를 확인한다.
        }
    }
}

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

안녕하세요, 이륙사입니다.

어제 백준에서 구간 나누기2 문제를 풀어봤습니다. 이전에 풀어본 유형이어서 알고리즘은 떠올랐지만 구체적인 풀이법이 떠오르지 않더라구요. 왜 그렇게 풀어야했는지 제대로 이해하지 못하고 넘어갔던 것 같아서 이번 기회에 정리해보려고 합니다.

선 정리

1. 구간을 어떻게 나눌까 -> 반대로 접근해서 구간 점수의 최대값을 기준으로 구간을 나눌 수 있는지 확인한다. -> 이분 탐색
2. 점수 최대값의 범위: 0 ~ (배열 최대값 - 최소값)
3. 구간을 나눌 때, 구간마다 최대한 길게 만든다 -> M개 이하가 될 확률을 높일 수 있음
   1. M개 이하로 나누는데 성공 -> 더 점수를 낮춰도 나눌 수 있는지 확인 -> upper = mid - 1
   2. M개 이하로 나누는데 실패 -> 점수를 더 높여서 확인 -> lower = mid + 1  
   3. 왜? 우리의 목표는 점수 최대 값의 최소값을 구하는 것이며, 구간 당 가능한 점수가 클수록 구간의 길이가 길어질 확률이 높아지기 때문이다. 

후 풀이

언뜻 읽어보면 점수의 최댓값의 최솟값, 말이 좀 복잡해 보입니다. 저는 구간을 나누면 점수가 계산되고 그 중 최댓값이 존재할텐데, 그 최댓값을 최소로 만들고 싶다. 즉, '구간을 어떻게 나눠야 가장 작은 (점수 최댓값: maxScore)을 구할 수 있을까'라고 이해했습니다. 

어떻게 구간을 나눠야 최소값을 얻을 수 있을까에 대한 문제구나 생각하고, 완전 탐색을 먼저 떠올렸습니다. 하지만 M개 이하로 나누기 때문에 시간 복잡도가 팩토리얼 수준으로 나와서 불가능하다고 판단했습니다.

반대로 접근한다

어떻게 해결할 수 있을까,,, 결론적으로 반대로 접근해서 해결할 수 있는 문제였습니다. 즉, 점수 최댓값을 먼저 설정하고, 그걸 기준으로 M개 이하의 구간을 나눌 수 있는지 확인하는 겁니다. 그 과정에서 이분 탐색을 사용합니다.

1. 점수 최대값의 범위는 배열이 하나일 때의 최소값 0에서 배열 내 최대값과 최소값의 차이 즉, 0 ~ (max(array) - min(array))입니다.
2. 이제 점수 (최대값)을 기준으로 구간을 나눠봅니다. 구간마다 최대한 많은 길이를 차지하도록 만듭니다. 왜냐면,
   1. M개 이하로 구간을 나눠야하기 때문에 구간을 최대한 길게 만들수록 성공 확률이 높아집니다.
   2. 앞의 구간에서 최대한 많은 숫자를 가져갈수록, 뒤에 남은 숫자들의 범위가 작아집니다. 그러면 그만큼 뒤에 구간의 점수도 작아질 확률이 높아집니다.
3. M개 이하로 구간을 만들지 못했다면, 점수를 더 크게 해서 구간을 나눌 수 있는지 다시 확인합니다. 반대로 성공했다면, 점수를 더 작게 해도 구간을 나눌 수 있는지 확인합니다. 이렇게 기준을 잡을 수 있는건, 점수가 클수록 구간이 길어질 확률이 높아지기 때문입니다. 즉, 평균적으로 구간마다 더 많은 숫자를 가질 수 있게 됩니다. 그리고, 우리의 목표는 점수 최대값의 최소값을 구하는 것이니까요!

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    // 입력
    val (n, divideLimit) = readLine().split(" ").map(String::toInt)
    val array = with(StringTokenizer(readLine())){
        IntArray(n){
            this.nextToken().toInt()
        }
    }
    
    var lower = 0
    var upper = array.maxOrNull()!! - array.minOrNull()!!

    if (n == 1) { // 배열 크기가 하나일 때
        print(0)
        return
    } else if (divideLimit == 1) { // 구간 1개 -> 배열을 나눌 수 없을 때
        print(upper - lower)
        return
    }

    // 점수의 최대값을 기준으로 이분 탐색
    // 점수의 최댓값이 mid가 되도록 구간을 가장 길게 나눠본다
    // 나눌 수 있으면 최소값을 찾기 위해 더 작은 최대값을 찾아본다
    // 나눌 수 없으면 더 큰 최대값을 찾는다
    // 구간의 점수가 커질수록 구간이 길어지고 구간 개수가 작아질 확률이 높아진다 
    while (lower <= upper) {
        val mid = (lower + upper) / 2

        if(isValid(array, mid, divideLimit)) {
            upper = mid - 1
        } else {
            lower = mid + 1
        }
    }

    print(lower)
}

fun isValid(array: IntArray, standard: Int, divideLimit: Int): Boolean {
    var count = 0
    var max = 0
    var min = 10_001

    for (i in array.indices) {
        max = max(max, array[i])
        min = min(min, array[i])

        // 최대값 or 최소값이 더 크/작아져서 더 길게 나눌 수 없을 때
        if (max - min > standard) {
            count++
            max = array[i]
            min = array[i]
        }
    }
    count++ // 마지막 구간

    return count <= divideLimit
}

후기

어떻게 생각하면 풀 수 있다는 건 확실히 알게됐지만, 왜 이렇게 접근해야만 하는지는 사실 아직도 와닿지가 않습니다. 이렇게 접근할 수도 있다는 걸 숙지하고, 사고의 폭을 넓혀가야 하는 걸까요? 조금은 답답하기도 한데, 이와 관련해서 댓글로 남겨주신다면 정말 감사하겠습니다.

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

안녕하세요, 이륙사입니다. 이번 게시물에서는 토너먼트 만들기 문제를 풀고 개인적으로 되돌아본 점을 기록했습니다.

핵심 아이디어

랭킹이 낮은(값이 큰) 선수들이 오래 남아 있을수록 랭킹 차의 합이 커진다.

왜냐면 토너먼트를 진행할수록 랭킹 값이 작은 선수들이 올라오기 때문에, 랭킹 값이 큰 선수들이 부전승으로 올라가면 항상 처음에 옆에 있던 선수들보다 랭킹 값이 같거나 작은 선수들과 맞붙게 된다.

ex) 1 4 2 5 3 7 - 랭킹차가 가장 작은 선수들부터 시합을 할 경우,

1 4 2 3 7 -> 1 4 2 7  -> 1 2 7 -> 1 2 -> 1 

만약 처음에 7과 3이 대결했다면 7에 의한 랭킹 차는 4로 끝났을 것이다.

따라서, 랭킹이 낮은 선수부터 우선적으로 게임을 진행시켜 떨어뜨린다.

회고

처음에 매 반복마다 랭킹 차가 작은 선수들부터 대결시키면 되겠구나 생각해서 틀렸다. 이후에 1 2 3 4 5 6 예시를 떠올리면서 랭킹차가 작은 선수들 중에서 값이 큰 선수들부터 대결시키면 되겠다 싶었는데, 그것도 아니었다.

사실 어떻게 위 아이디어를 떠올릴 수 있었을지 아직 잘 모르겠다.

랭킹 차이 합의 최소를 구한다 -> 위로 올라갈수록 랭킹이 높은 선수들이 남는다 -> 그들과 나중에 맞붙지 않도록 랭킹이 낮은 선수들을 먼저 떨어뜨린다.

이렇게 떠올릴 수 있었을까?

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.abs
import kotlin.math.min

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val rankings = MutableList(n) {
        st.nextToken().toInt()
    }

    print(getMinDiffSum(rankings))
}

fun getMinDiffSum(rankings: MutableList<Int>): Int {
    var sumOfDiff = 0 // 정답

    while (rankings.size > 1) {
        var maxRankIndex = 0

        // 랭킹이 가장 낮은(값이 큰) 선수를 찾는다
        for (i in 0 until rankings.size) {
            if (rankings[i] == rankings.size) {
                maxRankIndex = i
                break
            }
        }

        // 랭킹 차이가 더 작은 선수와 대결한다
        sumOfDiff += when {
            maxRankIndex == 0 -> abs(rankings[maxRankIndex] - rankings[maxRankIndex + 1])
            maxRankIndex == rankings.lastIndex -> abs(rankings[maxRankIndex] - rankings[maxRankIndex - 1])
            else -> min(
                abs(rankings[maxRankIndex] - rankings[maxRankIndex + 1]),
                abs(rankings[maxRankIndex] - rankings[maxRankIndex - 1])
            )
        }

        rankings.removeAt(maxRankIndex)
    }

    return sumOfDiff
}