구현 실력 향상을 위해

매일 실버 2문제, 골드 1문제 구현 문제를 풀기로 했다.
각 알고리즘도 잊지 않도록 실버 1, 골드 1문제를 풀기로 했다.

실버의 경우 30분 제한으로 문제를 풀고 (조금만 더 하면 풀 수 있겠다 싶으면 맥시멈 1시간)
골드의 경우 1시간 제한으로 문제를 풀려고 한다 (아예 감도 안오면 바로 해설 보기, 맥시멈 90분)

오늘 푼 문제

구현

실버 5. 셀프 넘버

문제 조건대로 쭉 진행하면 되는 문제다.

1. 첫번째 셀프넘버인 1 출력 후 1을 기준으로 쭉 D(n)을 진행한 뒤 등장한 숫자는 전부 True 표시
2. 다음 False인 숫자는 셀프 넘버이므로 출력 후 D(n) 진행
   10000 이하까지 2) 과정 반복

뭔가 테이블을 써서 하니까 dp 생각도 나고 좋았다.

def D(num):
    result = num
    str_num = str(num)
    for n in str_num:
        result += int(n)

    return result


table = [False] * 10001

table[0] = True

for i in range(1, 10001):
    if not table[i]:
        print(i)
        next_num = D(i)
        while next_num < 10001:
            table[next_num] = True
            next_num = D(next_num)

실버 3. 단어 뒤집기

이 문제 역시 주어진 조건대로 구현하면 되는 문제다.
체크할 부분은 다음과 같다.

현재 살펴보는 문자(s)가

1. "<"인 경우 tag True표시, 그대로 문자(s) 입력
2. ">"인 경우 tag False표시, 그대로 문자(s) 입력
3. " "인 경우
   3-1. tag True인 경우, 그대로 문자(s) 입력
   3-2. tag False인 경우, 지금까지의 문자(tmp) 뒤집어서 입력, 그대로 문자(s) 입력
4. 그 외의 경우
   4-1. tag True인 경우, 그대로 문자(s) 입력
   4-2. tag False인 경우, 뒤집기 위한 임시문자열(tmp)에 입력

• 끝까지 살펴보았고 뒤집어줘야할 문자가 존재하는 경우 result에 마지막으로 뒤집어서 넣어주기
• 사용자가 입력한 엔터를 삭제하기 위해 input().rstrip() 사용

from sys import stdin

input = stdin.readline

S = input().rstrip()

result = ""
tmp = ""
tag = False

for i, s in enumerate(S):
    if s == "<":
        if tmp != "":
            result += tmp[::-1]
        tmp = ""
        tag = True
        result += s
    elif tag and s != ">":
        result += s
    elif s == ">":
        tag = False
        result += s
    elif s == " " and tag:
        result += s
    elif s == " ":
        result += tmp[::-1]
        tmp = ""
        result += s
    else:
        tmp += s

    if i == len(S) - 1 and tmp != "":
        result += tmp[::-1]

print(result)

골드 4. 연구소

문제에서 요구하는 조건대로 쪼개서 구현하면 되는 문제다.
바이러스가 퍼진 뒤의 최대 안전 영역(0의 개수) 크기를 구하면 된다.

1. 벽을 세울 수 있는 모든 경우의 수 체크하기 (최대 입력값이 작아 완탐해도 된다)
2. 바이러스 전파 : goVirus()
3. 안전영역 세기 : countSafe()

from sys import stdin
import copy
from collections import deque
from itertools import combinations

input = stdin.readline

N, M = map(int, input().split(" "))  # row(y), col(x)

graph = []
blank = []
virus = []

# 입력 받기
for row in range(N):
    data = list(map(int, input().split(" ")))
    for col, d in enumerate(data):
        if d == 0:
            blank.append((row, col))
        if d == 2:
            virus.append((row, col))
    graph.append(data)

dy = [-1, 1, 0, 0]  # 상 하 좌 우
dx = [0, 0, -1, 1]


def goVirus(map):
    q = deque([])
    for virus_r, virus_c in virus:
        q.append((virus_r, virus_c))

    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dy[i]
            nc = c + dx[i]
            if 0 <= nc < M and 0 <= nr < N:
                if map[nr][nc] == 0:  # 빈칸
                    map[nr][nc] = 2  # 바이러스 전파
                    q.append((nr, nc))  # 새로운 칸 큐에 추가


def countSafe(map):
    result = 0
    for r in range(N):
        for c in range(M):
            if map[r][c] == 0:  # 빈칸이면
                result += 1  # 안전영역 + 1
    return result


result = 0
for comb in combinations(blank, 3):
    # 벽 세우기
    tmp_graph = copy.deepcopy(graph)
    for r, c in comb:
        tmp_graph[r][c] = 1

    goVirus(tmp_graph)
    result = max(result, countSafe(tmp_graph))

print(result)