노프스모 코테 스터디 2주차 - 1, 2, 3번

1, 2, 3번이 비슷하면서도 조금씩 달라서 세 문제를 한꺼번에 푸는 바람에 깨달은 바가 있어서 한 게시물로 올렸다

 

1. 백준 2630 - 색종이 만들기
https://www.acmicpc.net/problem/2630

 

from collections import deque

N = int(input())

matrix = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    matrix[i] = [int(x) for x in input().split(' ')]


# returns -1 if it contains different colors
# returns 0 or 1 as color if it contains only one color
def is_all_same_color(start_i, start_j, size):
    color = matrix[start_i][start_j]
    for i in range(start_i, start_i + size):
        for j in range(start_j, start_j + size):
            if color == matrix[i][j]:
                continue
            else:
                return -1
    return color


num_whites = 0
num_blues = 0
# deque 자료형을 queue로 쓰면서 BFS 순회를 한다
# queue에 들어가는 원소는 (시작 x좌표, 시작 y좌표, 종이 크기) 로 이루어진 tuple이다
q = deque()
q.append((0, 0, N))

while len(q) > 0:
    i, j, size = q.popleft()
    color = is_all_same_color(i, j, size)
    if color == 0:
        num_whites += 1
    elif color == 1:
        num_blues += 1
    else:
        q.append((i, j, int(size / 2)))
        q.append((i + int(size / 2), j, int(size / 2)))
        q.append((i + int(size / 2), j + int(size / 2), int(size / 2)))
        q.append((i, j + int(size / 2), int(size / 2)))

print(num_whites)
print(num_blues)

 

 

 

2. 백준 1992 - 쿼드트리
https://www.acmicpc.net/problem/1992

 

from collections import deque

N = int(input())

matrix = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    matrix[i] = [int(x) for x in input()]


# returns -1 if it contains different kinds of bit
# returns 0 or 1 if it contains only one kind of bit
def is_all_same_bit(start_i, start_j, size):
    bit = matrix[start_i][start_j]
    for i in range(start_i, start_i + size):
        for j in range(start_j, start_j + size):
            if bit == matrix[i][j]:
                continue
            else:
                return -1
    return bit


answer = ''

# DFS 순회를 하면서 서로 다른 비트로 이루어진 영상이 있다면 괄호를 추가하고 함수를 재귀 호출한다 
def dfs(i, j, size):
    global answer
    bit = is_all_same_bit(i, j, size)
    if bit == 0:
        answer += '0'
    elif bit == 1:
        answer += '1'
    else:
        answer += '('
        dfs(i, j, int(size / 2))
        dfs(i, j + int(size / 2), int(size / 2))
        dfs(i + int(size / 2), j, int(size / 2))
        dfs(i + int(size / 2), j + int(size / 2), int(size / 2))
        answer += ')'

dfs(0, 0, N)
print(answer)

 

1번 문제와 아주 비슷해 보여서 1번 문제의 코드를 최대한 재활용 해 보려고 했다.

첫 번째로는, bfs를 살리려고 했지만 괄호 추가하는 시점을 기억하기 위해 코드가 지저분해지고 말았다. 사실 돌지도 않았다.

두 번째로는, dfs 방식은 채택하되 함수 재귀 호출을 하지 않고 iteration을 하려고 했다. 마찬가지로 괄호 추가하는 시점을 잡기가 쉽지 않았다.

그래서 결국 가장 깔끔한 방법(dfs + 재귀 호출)으로 코드를 다시 짜서 통과했다.

 

 

3. 백준 1780 - 종이의 개수
https://www.acmicpc.net/problem/1780

 

from collections import deque

N = int(input())

matrix = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    matrix[i] = [int(x) for x in input().split(' ')]


# returns -2 if it contains different numbers
# returns -1 or 0 or 1 if it contains only one kind of number
def is_all_same_number(start_i, start_j, size):
    number = matrix[start_i][start_j]
    for i in range(start_i, start_i + size):
        for j in range(start_j, start_j + size):
            if number == matrix[i][j]:
                continue
            else:
                return -2
    return number


num_minus_one = 0
num_zero = 0
num_one = 0
# deque 자료형을 stack으로 사용한다
# stack에 들어가는 원소는 (시작 x좌표, 시작 y좌표, 종이의 크기) 로 이루어진 tuple이다
q = deque()
q.append((0, 0, N))

while len(q) > 0:
    i, j, size = q.pop()
    num = is_all_same_number(i, j, size)
    if num == 0:
        num_zero += 1
    elif num == 1:
        num_one += 1
    elif num == -1:
        num_minus_one += 1
    else:
        next_size = int(size / 3)
        for i_increase in [0, next_size, next_size*2]:
            for j_increase in [0, next_size, next_size*2]:
                q.append((i + i_increase, j + j_increase, next_size))

print(num_minus_one)
print(num_zero)
print(num_one)

 

이번에야 말로 1번과 같은 코드를 쓸 수 있을거라고 생각했다.

메모리 초과가 났다.

왜?? 같은 문제인데 메모리 초과가 나??? 하고 의아했는데, 종이를 4등분하지 않고 9등분하는 바람에 tree의 각 노드가 가지는 children이 4개가 아니라 9개로 늘었기 때문이었다. 그래서 BFS를 쓰면 저장해놓고 있어야 하는 원소가 많으므로 메모리 초과가 난 것이다.

그래서 눈물을 머금고 DFS로 교체했더니 문제없이 풀렸다

 

 

세 문제를 같이 풀면서..

완전 비슷한 문제인데 세 문제를 모두 다르게 풀게 되었다.

사실 1번 문제를 처음부터 DFS로 풀었다면 3번에는 같은 코드를 적용할 수 있었을 것 같다. 1번 문제를 BFS로 풀었지만 DFS가 더 유리하다는 걸 3번을 풀면서 알게 되었다.

 

전에 DFS와 BFS의 유불리에 대한 질문을 받아 본 적이 있는데 제대로 대답을 하지 못 했었다.

그런데 이번 문제를 풀면서 DFS가 유리한 경우를 알 것 같았다. tree의 node가 children을 많이 가질 수 있는 경우 bfs로 풀면 메모리를 많이 쓰게 되니까 dfs를 써서 한 우물만 파는 것이 유리할 것 같다.

반대로 bfs가 유리한 경우는 node의 children 수가 적을 때일까?

 

그리고 2번과 3번을 같은 코드로 풀 수 있을까? 도 좀 궁금하긴 하다. 왠지 2번 코드쪽으로 수렴해야 할 것 같은 느낌은 든다