출처: [백준] 2309번 일곱 난쟁이

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

예제 입력 1

1
2
3
4
5
6
7
8
9

20
7
23
19
10
15
25
8
13

예제 출력 1

1
2
3
4
5
6
7

7
8
10
13
19
20
23

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 초등부 1번
  • 어색한 표현을 찾은 사람: upple1

알고리즘 분류

• 브루트포스 알고리즘

소스코드1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import sys
from itertools import combinations

input = sys.stdin.readline

dwarfs = [int(input()) for _ in range(9)]
dwarfs.sort()

nPr = combinations(dwarfs, 7)

temp = []
for case in list(nPr):
    if sum(case) == 100:
        temp = case
        break
for x in temp:
    print(x)

소스코드2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys

input = sys.stdin.readline

dwarfs = [int(input()) for _ in range(9)]
dwarfs.sort()

height_sum = sum(dwarfs)
delete_element1 = 0
delete_element2 = 0

for i in range(9):
    for j in range(i + 1, 9):
        if height_sum - (dwarfs[i] + dwarfs[j]) == 100:
            delete_element1 = dwarfs[i]
            delete_element2 = dwarfs[j]
            break

for dwarf in dwarfs:
    if dwarf == delete_element1 or dwarf == delete_element2:
        continue
    else:
        print(dwarf)

출처: [백준] 12018번 Yonsei TOTO

문제

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.

성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.

그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

입력

첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ Pi ≤100, 1 ≤ Li ≤ 100)

(단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)

출력

첫째 줄에 주어진 마일리지로 최대로 들을 수 있는 과목 개수를 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11

5 76
5 4 
36 25 1 36 36
4 4
30 24 25 20
6 4
36 36 36 36 36 36
2 4
3 7
5 4
27 15 26 8 14

예제 출력 1

1

4

출처

• • University > 연세대학교 > 2016 연세대 컴퓨터과학과 프로그래밍 경진대회 A번
    • 문제를 만든 사람: zych1751

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
answer = 0
sugang = []

for _ in range(N):
    P, L = map(int, input().split())
    mileages = list(map(int, input().split()))
    heapq.heapify(mileages)

    available = L - P
    if available > 0:
        heapq.heappush(sugang, 1)
    else:
        for i in range(abs(available)):
            heapq.heappop(mileages)
        heapq.heappush(sugang, heapq.heappop(mileages))

count = 0
while sugang:
    sugang_mileage = heapq.heappop(sugang)
    if M - sugang_mileage >= 0:
        M -= sugang_mileage
        count += 1
    else:
        break
print(count)

출처: [백준] 15903번 카드 합체 놀이

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력 1

1
2

3 1
3 2 6

예제 출력 1

1

16

예제 입력 2

1
2

4 2
4 2 3 1

예제 출력 2

1

19

출처

• University > 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회 > UCPC 2018 예선 B번
  • 문제를 만든 사람: haden

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 우선순위 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
card_list = list(map(int, input().split()))

heapq.heapify(card_list)  # card_list를 heap으로 변환

for _ in range(M):
    x, y = heapq.heappop(card_list), heapq.heappop(card_list)
    for _ in range(2):
        heapq.heappush(card_list, x + y)


print(sum(card_list))

출처: [백준] 11725번 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1

1
2
3
4
5
6
7

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

1
2
3
4
5
6

4
6
1
3
1
4

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2

1
2
3
4
5
6
7
8
9
10
11

1
1
2
3
3
4
4
5
5
6
6

출처

• 문제를 만든 사람: baekjoon
• 잘못된 조건을 찾은 사람: jh05013

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())

trees = {}
for i in range(N):
    trees[i + 1] = set()

for i in range(N - 1):
    a, b = map(int, input().split())
    trees[a].add(b)
    trees[b].add(a)

parents = [False] * (N + 1)


def dfs(graph, v, visited):
    for i in graph[v]:
        if not visited[i]:
            visited[i] = v
            dfs(graph, i, visited)


dfs(trees, 1, parents)
for i in range(2, N + 1):
    print(parents[i])

출처: [백준] 1987번 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1

1
2
3

2 4
CAAB
ADCB

예제 출력 1

1

3

기타 입력

1
2
3
4

3 4
ABBC
ECED
FGDH

기타 출력

1

8

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2002 > Regional Competition - Juniors 3번

• 데이터를 추가한 사람: august14, doju, jh05013

링크

• PKU Judge Online

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import sys

input = sys.stdin.readline

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


def dfs(x, y, count):
    global ans
    ans = max(ans, count)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C and passed[board[nx][ny]] == 0:
            passed[board[nx][ny]] = 1
            dfs(nx, ny, count + 1)
            passed[board[nx][ny]] = 0


R, C = map(int, input().split())
board = [list(map(lambda x: ord(x) - 65, input().rstrip())) for _ in range(R)]
passed = [0] * 26

ans = 1
passed[board[0][0]] = 1
dfs(0, 0, ans)

print(ans)

소스코드_BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

input = sys.stdin.readline

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


def bfs():
    global count
    queue = set()
    queue.add((0, 0, board[0][0]))

    while queue:
        x, y, ans = queue.pop()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in ans:
                queue.add((nx, ny, ans + board[nx][ny]))
                count = max(count, len(ans) + 1)


R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
count = 1
bfs()
print(count)

소스코드_실패(메모리 초과)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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


def dfs(x, y, cnt):
    global count
    count = max(cnt, count)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in passed:
            passed.append(board[nx][ny])
            dfs(nx, ny, cnt + 1)
            passed.append(board[nx][ny])


R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
passed = []
count = 1
dfs(0, 0, count)
print(count)

출처: [백준] 2644번 촌수계산

문제

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

예제 출력 1

1

3

출처

Olympiad > 한국정보올림피아드 > KOI 1999 > 중등부 1번

• 문제의 오타를 찾은 사람: dkdsla12, YunGoon
• 빠진 조건을 찾은 사람: jh05013

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import sys

input = sys.stdin.readline

N = int(input())
comp1, comp2 = map(int, input().split())
M = int(input())
family = {}
for i in range(N):
    family[i + 1] = set()
for i in range(M):
    x, y = map(int, input().split())
    family[x].add(y)
    family[y].add(x)



def dfs(graph, target, count):
    visited[target] = count
    for i in graph[target]:
        if not visited[i]:
            dfs(graph, i, count + 1)


visited = [False] * (N + 1)
dfs(family, comp2, 1)
if not visited[comp1]:
    print(-1)
else:
    print(visited[comp1] - 1)

출처: [백준] 21567번 숫자의 개수2

문제

세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오.

예를 들어 A = 150, B = 266, C = 427 이라면 A × B × C = 150 × 266 × 427 = 17037300 이 되고, 계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에는 A × B × C의 결과에 0 이 몇 번 쓰였는지 출력한다. 마찬가지로 둘째 줄부터 열 번째 줄까지 A × B × C의 결과에 1부터 9까지의 숫자가 각각 몇 번 쓰였는지 차례로 한 줄에 하나씩 출력한다.

예제 입력 1

1
2
3

150
266
427

예제 출력 1

1
2
3
4
5
6
7
8
9
10

3
1
0
2
0
0
0
2
0
0

예제 입력 2

1
2
3

1
1
1

예제 출력 2

1
2
3
4
5
6
7
8
9
10

0
1
0
0
0
0
0
0
0
0

예제 입력 3

1
2
3

999999
999999
999999

예제 출력 3

1
2
3
4
5
6
7
8
9
10

5
0
1
0
0
0
0
1
0
11

출처

알고리즘 분류

• 구현

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys

input = sys.stdin.readline

A = int(input())
B = int(input())
C = int(input())
product_value = A * B * C

split_num = list(str(product_value).rstrip())

num_dict = {}

for i in range(10):
    num_dict[i] = 0

for num in split_num:
    num_dict[int(num)] += 1

for i in range(10):
    print(num_dict[i])

출처: [백준] 10026번 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

1
2
3
4
5

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1

1
2
3
4
5
6

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1

1

4 3

출처

Olympiad > USA Computing Olympiad > 2013-2014 Season > USACO March 2014 Contest > Bronze 3번

• 문제를 번역한 사람: baekjoon
• 어색한 표현을 찾은 사람: corea

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(matrix, x, y, value):
    matrix[x][y] = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < N and 0 <= ny < N:
            if matrix[nx][ny] == value:
                dfs(matrix, nx, ny, value)


N = int(input())
grid = [list(input().rstrip()) for _ in range(N)]  # people(R,G,B)
grid2 = [[0] * N for _ in range(N)]  # people(R=G, B)

for i in range(N):
    for j in range(N):
        if grid[i][j] == 'R' or grid[i][j] == 'G':
            grid2[i][j] = 1
        else:
            grid2[i][j] = 2

rgb_count = 0
b_count = 0
for i in range(N):
    for j in range(N):
        if grid[i][j] != 0:
            dfs(grid, i, j, grid[i][j])
            rgb_count += 1

        if grid2[i][j] != 0:
            dfs(grid2, i, j, grid2[i][j])
            b_count += 1

print(rgb_count, b_count)

출처: [백준] 2583번 영역 구하기

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

img

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

예제 입력 1

1
2
3
4

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

예제 출력 1

1
2

3
1 7 13

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 고등부 2번

• 문제의 오타를 찾은 사람: alphago92
• 데이터를 추가한 사람: hjhj97
• 잘못된 데이터를 찾은 사람: kookmin20103324

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y, count):
    ground[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < M and 0 <= ny < N:
            if ground[nx][ny] == 0:
                count = dfs(nx, ny, count + 1)
    return count


M, N, K = map(int, input().split())
ground = [[0] * N for _ in range(M)]

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())

    for i in range(y1, y2):
        for j in range(x1, x2):
            ground[i][j] = 1

count = []
for i in range(M):
    for j in range(N):
        if ground[i][j] == 0:
            count.append(dfs(i, j, 1))

print(len(count))
for x in sorted(count):
    print(x, end=" ")

출처: [백준] 2468번 안전 영역

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

img

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

img

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

img

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제 입력 1

1
2
3
4
5
6

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

예제 출력 1

1

5

노트

아무 지역도 물에 잠기지 않을 수도 있다.

출처

Olympiad > 한국정보올림피아드 > KOI 2010 > 초등부 2번

• 문제의 오타를 찾은 사람: apjw6112
• 어색한 표현을 찾은 사람: jh05013
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 브루트포스 알고리즘
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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


def dfs(x, y, h):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < N and 0 <= ny < N and ground[nx][ny] > h and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny, h)


N = int(input())
ground = [list(map(int, input().split())) for _ in range(N)]

result = 0
for k in range(max(max(ground))):
    count = 0
    visited = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if ground[i][j] > k and not visited[i][j]:
                count += 1
                visited[i][j] = True
                dfs(i, j, k)
    result = max(result, count)
print(result)