졍's 기술 블로그

단지번호붙이기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너무 우선 탐색, 깊이 우선 탐색

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입출력

Algorithm

BFS
1. 그래프 구현
2. 단지에 포함되어있고(graph[x][y] == 1), 방문한 적이 없다면(not visited[x][y]) bfs 수행
-> 이 때 home_cnt 라는 리스트에(각 단지의 아파트 개수) 마지막 원소(0) append
3. bfs 수행하면서 아파트 하나씩 만날 때 마다 home_cnt의 마지막 원소 증가
4. bfs 수행 완료 후 home_cnt의 마지막 원소가 0인 경우(시작 위치 제외하고 만난 아파트가 없는 경우) manually 1 증가
5. home_cnt 리스트 sort 후 length, 원소 하나씩 출력

Code

from collections import deque
queue = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(graph, sx, sy, visited):
    queue.append((sx, sy))

    while queue:
        x, y = queue.popleft()

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

            # graph 벗어나면 continue
            if nx < 0 or nx > N-1 or ny < 0 or ny > N-1:
                continue

            # 0이면 continue
            if not graph[nx][ny]:
                continue

            # 방문한 적 있으면 continue
            if visited[nx][ny]:
                continue

            # 방문 기록
            cnt_home[-1] += 1
            visited[nx][ny] = True
            queue.append((nx,ny))
    
N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

cnt_home = []
visited = [[False for _ in range(N)] for _ in range(N)]
for x in range(N):
    for y in range(N):
        queue.clear()
        if graph[x][y] and not visited[x][y]:
            cnt_home.append(0)
            bfs(graph, x, y, visited)
            if not cnt_home[-1]:
                cnt_home[-1] += 1

cnt_home.sort()
print(len(cnt_home))
for i in cnt_home:
    print(i)

메모리: 34184 KB
시간: 64 ms

미로 탐색

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 192 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입출력

Algorithm

BFS
1. 그래프 구현
2. BFS 돌면서 문제 조건에 따라 갈 수 없는 곳이 아니라면 큐에 모두 추가
3. 도착지점에 도착하면 이동 횟수 return

Code

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(graph, sx, sy, ex, ey, visited):
    queue = deque()
    queue.append((sx, sy))

    while queue:
        x, y = queue.popleft()

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

            # 도착지에 도착하면 return
            if nx == ex and ny == ey:
                return visited[x][y] + 1
            
            # graph 밖으로 나가면 continue
            if nx < 0 or nx > N-1 or ny < 0 or ny > M-1:
                continue

            # 방문한 적 있으면 continue
            if visited[nx][ny]:
                continue

            # 0이면 continue
            if not graph[nx][ny]:
                continue

            # 방문 기록
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx, ny))

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

graph = []
visited = [[0 for _ in range(M)] for _ in range(N)]
for _ in range(N):
    graph.append(list(map(int, input())))

print(bfs(graph, 0, 0, N-1, M-1, visited)+1)

메모리: 34168 KB
시간: 76 ms

경로 찾기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 플로이드-워셜

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입출력

Algorithm

DFS
1. 그래프 구현
2. DFS 돌면서 갈 수 있는 곳 리스트에 저장
3. 리스트에 들어있는 곳에 맞게 1로 변경

Code

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(x):
    global idx
    # 현재 노드에 방문한 적 있는지 확인
    if visited[x]:
        return False
    
    # 방문 기록
    # dfs를 첫 번째 수행하는 경우가 아닐 때만 수행
    if x != idx or (nodes and x == idx):
        visited[x] = True
        nodes.append(x)
    
    # 인접 노드 방문
    for next_node in graph[x]:
        dfs(next_node)
    
    return True

def set_answer(i):
    for j in nodes:
        answer[i][j] = 1
        
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
answer = [[0 for _ in range(N)] for __ in range(N)]
# 그래프 구현
graph = [[] for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 1:
            graph[i].append(j)

# 모든 정점 DFS 돌기
for idx in range(N):
    nodes = []
    visited = [False for _ in range(N+1)]
    
    if dfs(idx):
        # set answer
        set_answer(idx)

for i in range(N):
    print(' '.join(map(str, answer[i])))

메모리: 30840 KB
시간: 92 ms

행렬

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 그리디 알고리즘

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

예제 입출력

Algorithm

구현 - Simulation
1. 다른 숫자인 곳을 왼쪽 위 지점으로 잡고 연산
2. 모두 변환 후 A와 B가 동일한지 비교

Code

# [x][y]의 위치의 값이 같은지 다른지 확인
def is_same(x, y):
    if A[x][y] != B[x][y]:
        return False
    else:
        return True

# [x][y]의 위치의 값을 변경
def change(x, y):
    # [x][y]부터 3x3이 범위를 벗어나면 for문 들어가지 않음
    if x+3 > N or y+3 > M:
        return False
    
    for xx in range(x, x+3):
        for yy in range(y, y+3):
            # 0이면 1로 변경
            if A[xx][yy] == 0:
                A[xx][yy] = 1
            else:
                A[xx][yy] = 0
    return True

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = [list(map(int, input().rstrip())) for _ in range(N)]
B = [list(map(int, input().rstrip())) for _ in range(N)]

answer = 0
for x in range(N):
    for y in range(M):
        # 다른 숫자인 곳이 있으면
        if not is_same(x, y):
            # 해당 위치부터 3x3 만큼 연산
            if change(x, y):
                answer += 1

# A와 B가 같으면 answer 출력
if A==B:
    print(answer)
# 같지 않으면 -1 출력
else:
    print(-1)

메모리: 30840 KB
시간: 76 ms

카드 합체 놀이

티어 : Silver 1
시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 자료 구조, 그리디 알고리즘, 우선순위 큐

문제

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

아기 석환이는 자연수가 쓰여진 카드를 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)

출력

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

예제 입출력

Algorithm

구현
1. 숫자 오름차순
2. 가장 맨 앞 두 숫자 더한 값으로 대체
3. 1과 2를 m번 반복

Code

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cards = list(map(int, input().split()))

for count in range(m):
    # 숫자 오름차순
    cards.sort()
    cards[0], cards[1] = cards[0]+cards[1], cards[0]+cards[1]

print(sum(cards))

메모리: 30840 KB
시간: 240 ms

영역 구하기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

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

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

<그림 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개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

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

예제 입출력

Algorithm

DFS
1. 입력받은 꼭지점을 기준으로 사각형의 값 1로 채움
2. DFS를 통해 0인 공간의 개수와 넓이 구하기

Code

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

def dfs(x, y):
    global count

    # graph 밖으로 벗어나거나 1이면 False 반환
    if x < 0 or y > M-1 or y < 0 or x > N-1:
        return False
    
    # 이미 방문한 곳이면 False 반환
    if visited[x][y] or graph[x][y] == 1:
        return False
    
    # 방문 기록
    visited[x][y] = True
    # 칸 수 세기
    count += 1
    
    # 인접 노드로 이동
    dfs(x-1, y)
    dfs(x+1, y)
    dfs(x, y-1)
    dfs(x, y+1)
    
    return True

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

# 입력받은 좌표를 기준으로 사격형의 값을 1로 채움
graph = [[0 for yy in range(M)] for xx in range(N)]
visited = [[False for yy in range(M)] for xx in range(N)]
for x1, y1, x2, y2 in inputs:
    for x in range(x1, x2):
        for y in range(y1, y2):
            graph[x][y] = 1

# DFS 이용해 0인 공간의 개수와 넓이 구하기
answer = [0]
for x in range(N):
    for y in range(M):
        count = 0
        if dfs(x, y):
            answer[0] += 1
            if count != 0:
                answer.append(count)

print(answer[0])
answer = answer[1:]
answer.sort()
print(' '.join(map(str, answer)))

메모리: 40684 KB
시간: 88 ms

마인크래프트

티어 : Silver 2
시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 1024 MB
알고리즘 분류 : 구현, 브루트포스 알고리즘

문제

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

입력

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

예제 입출력

Algorithm

구현
1. 기준 높이보다 높은 블럭의 차이 모두 합하기
2. 기준 높이보다 낮은 블럭의 차이 모두 합하기
3. 기준 높이만큼 쌓을 수 있는 블럭이 존재하면 answer 갱신

Code

import sys
input = sys.stdin.readline

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

max_height = 0
min_height = 256
for x in range(len(graph)):
    for y in graph[x]:
        max_height = max(max_height, y)
        min_height = min(min_height, y)

answer = [(256*2+256)*M*N, max_height]
height = max_height
while height >= min_height:
    # 기준 높이보다 높은 블럭의 차이 모두 합하기
    # 기준 높이보다 낮은 블럭의 차이 모두 합하기
    tall = 0
    short = 0
    for x in range(len(graph)):
        for y in range(len(graph[x])):
            if graph[x][y] > height:
                tall += (graph[x][y] - height)
            elif graph[x][y] < height:
                short += (height - graph[x][y])

    # 기준 높이만큼 쌓을 수 있는 블록이 충분히 존재하면 answer 갱신
    if (B+tall) >= short:
        if answer[0] > tall * 2 + short:
            answer = [tall * 2 + short, height]
    
    # 기준 높이를 낮춰 재검사
    height -= 1
        
print(answer[0], answer[1])

메모리: 117584 KB
시간: 900 ms

과자 나눠주기

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 이분 탐색, 매개 변수 탐색

문제

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

입력

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.

출력

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

예제 입출력

Algorithm

이진탐색
1. 과자의 길이를 오름차순 정렬
2. 중간 값을 찾아 해당 길이로 과자 만들기
3-1. 아이의 수보다 부족하면 왼쪽부분 탐색
3-2. 아이의 수보다 많으면 오른쪽 탐색

Code

import sys
input = sys.stdin.readline

M, N = map(int, input().split())
snack = list(map(int, input().split()))
answer = 0

# 과자의 길이를 오름차순 정렬
snack.sort()

# 이진탐색
start = 1
end = snack[-1]
while start <= end:
    # 중심값 찾기
    mid = (start+end)//2
    
    # 해당 길이로 과자 만들기
    count = 0
    for x in snack:
        if x >= mid:
            # 나눠줄 수 있는 조카의 수 = 과자를 mid 길이로 나누었을 때의 몫의 합
            count += x//mid
            
    # 과자 개수가 조카 수보다 적으면 왼쪽 부분 탐색 (더 짧은 과자 길이 찾기)
    if count < M:
        end = mid - 1
    # 과자 개수가 조카 수보다 많으면 오른쪽 부분 탐색 (더 긴 과자 길이 찾기)
    else:
        answer = mid
        start = mid + 1

print(answer)

메모리: 239748 KB
시간: 868 ms