서린이의 기술 블로그

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

1. 메인 아이디어

- l(=left)와 r(=right)를 고려한다. (left는 바구니 왼쪽, right는 바구니 오른쪽)

- 바구니의 길이가 1이기 때문에 시작 l = 1, r = 1 이다 ( r = 2 가아님, 2가되면 바구니의 길이가 2임)

- l을 통하여 r을 정의하면, r = l + m - 1

- 바구니가 사과보다 왼쪽, 오른쪽에 있을 때를 고려한다.

2. 소스코드

import sys
input = sys.stdin.readline

# 5 1
# 3
# 1
# 5
# 3

#     1      2    3   4  5
# |        |   |   |   |   |
# |        |   |   |   |   |
# |        |   |   |   |   |
# l=1,   r =1 , r은 2가아님, 왜냐하면 바구니 길이가 1이기 때문

n, m = map(int, input().split())
J = int(input())
l, ret = 1, 0 # r = l + m - 1 -> r = 1

for i in range(J):
    r = l + m - 1
    apple = int(input())
    if l <= apple <= r: continue
    else:
        if apple < l: # 사과보다 바구니가 오른쪽
            ret += l - apple
            l = apple
        else: # 바구니가 사과보다 왼쪽
            l += apple - r
            ret += apple - r
print(ret)

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

1. 풀이 알고리즘 : DFS(선택), BFS, 분할정복

2. 핵심 아이디어

   2-1. 입력값 하나하나를 행렬에 원소로 담기

   2-2. (0,0)과 size로부터 시작

   2-3. 한번에 4개씩 재귀적으로 호출하며, 각각 재귀는 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래와 size / 2를 계속 매개변수로 담아서, size가 1이 될 때까지 계속 호출한다.

   2-4. 문제 조건에 따라서 ret에 계속 String을 담아서 값을 만들어 호출한다.

3. 분할정복 알고리즘의 순차적 흐름 예시

4. 소스 코드

import sys

input = sys.stdin.readline

def quard(y, x, size):
    y = int(y)
    x = int(x)
    size = int(size)
    if size == 1:
        return str(a[y][x]) # 기저 조건(=종료 조건), size가 1일 때는 더 이상 쪼개지지 않는다.
    b = a[y][x] # 1개를 뽑아냄
    ret = ''
    for i in range(y, y + size): # y로 부터 size만큼 쪼갠다
        for j in range(x, x + size): # x로 부터 size만큼 쪼갠다
            if b != a[i][j]:
                ret += '('
                ret += quard(y, x, size / 2) # 왼쪽 위
                ret += quard(y, x + size / 2, size / 2) # 오른쪽 위
                ret += quard(y + size / 2, x, size / 2) # 왼쪽 아래
                ret += quard(y + size / 2, x + size / 2, size / 2) # 오른쪽 아래
                ret += ')'
                return ret
    return str(a[y][x])

n = int(input())
a = [[0] * n for _ in range(n)]
s = ''

for i in range(n):
    s = input()
    for j in range(n):
        a[i][j] = s[j]

print(quard(0, 0, n))

5. 소스 코드의 시각화

출처 : https://www.acmicpc.net/problem/2583

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

m, n, k = map(int, input().split())

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

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

visited = [[0] * m for _ in range(n)]

for i in range(k):
    s = a[i]
    for i in range(n):
        for j in range(m):
            if s[0] <= i < s[2] and s[1] <= j < s[3]:
                visited[i][j] = 1

s_list = []
tmp_list = []

def dfs(x, y):
    visited[x][y] = 1
    tmp_list.append(1)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if visited[nx][ny] == 0:
            dfs(nx, ny)

for i in range(n):
    for j in range(m):
        if visited[i][j] == 0:
            dfs(i, j)
            s_list.append(sum(tmp_list))
            tmp_list.clear()

s_num = len(s_list)
print(s_num if s_num > 0 else 1)
print(*sorted(s_list))

1. 풀이 알고리즘 : DFS(선택), BFS, 인접 리스트 etc

2. 핵심 아이디어

   2-1. K 개의 사각형 영역을 먼저 방문처리

   2-2. 방문되지 않은 영역을 깊이우선탐색하여 영역의 넓이과 갯수를 구함

   2-3. 다른 풀이 방법 :

K 개의 사각형 영역을 먼저 방문하지 않고, 방문되어야할 영역을 한번에 걸러서 처리하면 더 빠를 것으로 생각함

BFS로도 풀어보면 좋을 것 같음

3. 어려웠 던 부분

  3-1. (0,0) 의 위치가 왼쪽 하단에 있어서 Matrix를 만들 때 너무 헷갈려서, n과 m을 거꾸로 넣어버림

  3-2. 탐색 시 영역의 넓이를 누적하는 로직을 스택 함수에 넣었더니, 스택을 빠져나오면서 값이 원복되었음

-> tmp_list에 1씩 담아서 나중에 s_list에 담기 전에 sum()을 통해 누적합 하여 해결함

-> 다른 방법이 있는지 탐구 필요

4. 코드 개선

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

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

m, n, k = map(int, input().split())

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

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

visited = [[0] * m for _ in range(n)]

for i in range(k):
    s = a[i]
    for i in range(n):
        for j in range(m):
            if s[0] <= i < s[2] and s[1] <= j < s[3]:
                visited[i][j] = 1

s_list = []

def dfs(x, y):
    visited[x][y] = 1
    ret = 1 # dfs 들어갈때마다 1을 return하기위해서 ret = 1로 둠, 가중치가 2면 ret = 2 로 해야함
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if visited[nx][ny] == 0:
            ret += dfs(nx, ny) # 모든 dfs 의 결과값인 return ret을 ret에 더한다
    return ret

for i in range(n):
    for j in range(m):
        if visited[i][j] == 0:
            s_list.append(dfs(i, j))

s_num = len(s_list)
print(s_num if s_num > 0 else 1)
print(*sorted(s_list))

1. s_list에 담는 시점에 dfs(i, j)를 호출

2. ret = 1인 이유는, 가중치가 1이기 때문임 -> dfs 깊이를 들어간 만큼 return ret (=1) 을 계속 반환

3. 반환한 값들을 ret += dfs(nx, ny)에서 모두 더함 -> 빈 영역의 넓이 = 사각형의 갯수

4. 다 더한 후에 s_list.append(dfs(i, j))를 통하여, 빈 영역의 넓이를 담는다.

5. 빈 영역이 총 3개 이고 각각 1, 7, 13 이다