[백준]2617. 구슬찾기

문제 링크: problem-link

첫번째 풀이 시도 : 플로이드 워셜 알고리즘

백준 1613 역사 문제1613-link와 같이 플로이드 워셜 알고리즘으로 해결할 수 있었다.

구슬의 무게 관계가 입력으로 주어지기 때문에 주어진 관계 정보로 유추할 수 있는 관계 정보를 플로이드 워셜 알고리즘으로 찾아낸다.

map[i][j] 가 -1인 경우 i가 j보다 가볍다는 것이다. 반대로 map[i][j]가 1인 경우 i가 j보다 무겁다는 것이다.

// 플로이드 방식
for (int m = 1; m <= N; m++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {

            if (map[i][m] == -1 && map[m][j] == -1) {
                // i -> m -> j로 무겁다면
                map[i][j] = -1;
                map[j][i] = 1;
            }

        }
    }
}

유추할 수 있는 관계 정보를 모두 찾아낸 후 각 구슬 마다 자신보다 무거운 구슬, 가벼운 구슬을 카운트한다.

구슬의 무게가 중간인 경우 중간인 구슬보다 작은 구슬의 개수는 다음과 같다.

중간 구슬 보다 가벼운 구슬의 개수 = (N - 1) / 2

중간 구슬 보다 무거운 구슬의 개수 = N - (N + 1) / 2 

구슬의 무게가 중간이려면 최소한 ‘중간 구슬 보다 가벼운 구슬의 개수’보다 현재 유추할 수 있는 가벼운 구슬의 개수가 많으면 안된다.

또한 최소한 ‘중간 구슬 보다 무거운 구슬의 개수’보다 현재 유추할 수 있는 무거운 구슬의 개수가 많으면 안된다.

int lightMax = (N - 1) / 2;
int heavyMax = N - (N + 1) / 2;

int answer = 0;
for (int i = 1; i <= N; i++) {
    int lightNum = 0, heavyNum = 0;
    for (int j = 1; j <= N; j++) {

        if(map[i][j] == -1)
            heavyNum++;
        else if(map[i][j] == 1)
            lightNum++;

    }
    if (lightNum > lightMax || heavyNum > heavyMax)
        answer++;
}

Todo. 1613 역사, 2617 구슬찾기 문제를 DFS로도 풀어보자.

Github 링크: github-link