구현

실버2. 백준 18111 마인크래프트

풀이

문제에서 어떻게 풀라고 다 알려주는 구현문제보다도, 이 문제가 완전탐색이구나 깨닫는 것은 아직 잘 감이 안온다. 이틀을 붙잡고 있다가 해설을 봤다. (그렇게 어려운 문제가 아니었음에도!!)

이 문제는 가능한 높이 경우가 0~256 사이의 자연수로 모든 높이의 경우에 대해 완전탐색을 해도 된다.

0~256 사이의 높이 curr_h 에 대해서 모든 블럭의 높이를 살펴보며 그 높이에 맞추려면 1. 쌓아야 하는지 2. 깎아야 하는지 체크해주면 된다.

1. 쌓아야하는 경우 use 변수에 쌓아야 하는 블록의 수를 더해준다.
2. 깎아야하는 경우 save 변수에 깎아야 하는 블록의 수를 더해준다.

만약 사용한 블록의 수 (use) 가 사용 가능한 전체 블록의 수 (B + save)보다 많다면 그 경우는 체크하지 않는다.

블록을 쌓는 경우에는 2초 소요, 블록을 깎는 경우에는 1초가 소요되므로 전체 소요되는 시간은 use + save * 2가 된다. 만약 가능한 경우가 여러개 있다면 가장 높은 땅의 높이를 출력해야 하므로 최댓값이 갱신될 때마다 땅의 높이도 함께 갱신해준다.

코드

각 블록의 높이를 2차원 배열로 받아 N^3의 시간복잡도를 사용하면 시간초과가 날 수 있다. 따라서 블록의 좌표값은 따로 고려할 사항이 아니므로 높이별로 블록의 개수를 저장해주는 딕셔너리를 사용했다.

아래 코드는 python3로 통과한다.

from sys import stdin

input = stdin.readline

N, M, B = map(int, input().split(" "))
heights = {}

for _ in range(N):
    data = list(map(int, input().split(" ")))
    # 해당 높이의 블록 갯수 세기
    for i in data:
        heights[i] = heights.get(i, 0) + 1

answer = int(1e9)
ground_height = 0

# 깎아서 저장한 블록의 수 : save
# 인벤에서 가져와 쌓은 블록의 수 : use
for curr_h in range(257):
    save = 0
    use = 0
    for height in heights:
        # 블록 쌓기
        if height < curr_h:
            use += (curr_h - height) * heights[height]
        # 블록 깎기
        else:
            save += (height - curr_h) * heights[height]

    # 깎은 블록의 수가 사용 가능한 블록의 수보다 크다면 고려X
    if use > save + B:
        continue

    time = save * 2 + use
    if time <= answer:
        answer = time
        ground_height = curr_h

print(answer, ground_height)

구현 + 그리디

실버3. 백준 1783 병든 나이트

풀이

DFS, BFS로 풀었다가 시간 초과도 나고, 어떻게 접근해야될지도 모르겠어서 1시간정도 고민하고 해설을 찾아봤다. 오늘 푸는 문제 다 해설 보는 것 같다... 슬프다.

주의할 점은 지나가는 칸은 방문한 것X, 최종 이동을 마친 칸만 방문O이라는 점이다!

이 문제는 가로, 세로 길이에 따라 최적의 경우가 정해져 있다. (그리디)

1. 가로 길이가 1인 경우 (N=1) : 이동 불가
2. 가로 길이가 2인 경우 (N=2) : URR + DRR 패턴만 섞어서 이동이 가능. 문제에서 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다고 했으므로, 4번 이상 넘어가는 경우 더이상 이동이 불가능하다.
3. 가로 길이가 3 이상인 경우 (N>=3) : 세로 길이가 7 이상인 경우 모든 패턴을 다 사용할 수 있다. 왼쪽으로 이동하는 경우는 없기 때문에 가로 길이가 3이상인 경우, 모든 패턴을 다 사용한 뒤에는 UUR + DDR 패턴으로만 이동해야 가장 많이 방문할 수 있다.
   만약 세로 길이가 7보다 작다면, UUR + DDR 패턴으로만 이동해야 가장 많이 방문할 수 있다.

코드

from sys import stdin

input = stdin.readline

N, M = map(int, input().split(" "))  # 세로 길이 N (row) 가로길이 M (col)

answer = 0
if N == 1:
    answer = 1
elif N == 2:
    if 1 <= M <= 6:
        answer = (M + 1) // 2
    else:
        answer = 4
elif N >= 3:
    if 1 <= M <= 6:
        answer = min(M, 4)
    else:
        answer = M - 2

print(answer)

어려운 문제가 이렇게 간결하게 최종 코드로 완성되면 알고리즘 공부를 열심히 해야겠다고 느낀다. 이 문제가 실버 3단계정도라니....

골드5. 백준 14503 로봇 청소기

풀이

삼성 SW 역량 테스트 기출 문제다. 삼성 문제는 정말 문제에서 시키는대로 차근차근 구현하면 된다.

BFS 방식을 사용하기 위해 deque를 사용했다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
-> 살펴봐야 하는 칸을 큐에서 꺼내 값이 0(청소X칸)인 경우 2로 변경 (청소O 칸)
벽과 구분해주기 위해 값 2를 사용했다

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
-> is_unclean 플래그를 사용해서 체크
2-1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
-> 후진하는 방법은 현재 방향에서 -2를 빼준 뒤 4로 나눈 나머지로 계산 (북쪽을 바라보고 있는 경우, 남쪽으로 이동하면 된다)
-> 큐에 좌표값 삽입
2-2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
-> return으로 함수 빠져나가기

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
-> is_unclean 플래그가 참이라면
3-1. 반시계 방향으로 90도 회전한다.
-> d -= 1, d %= 4
3-2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
-> 만약 조건에 해당하지 않으면 계속 회전시킨다.
3-3. 1번으로 돌아간다.
-> 큐에 좌표값 삽입

코드

from sys import stdin
from collections import deque

input = stdin.readline

N, M = map(int, input().split(" "))  # row : N, col : M
R, C, d = map(int, input().split(" "))

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

# d : 0 북 / 1 동 / 2 남 / 3 서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]


def clean(q):
    global N, M, d
    while q:
        r, c = q.popleft()
        # 1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
        if graph[r][c] == 0:
            graph[r][c] = 2

        is_unclean = False
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < M and graph[nr][nc] == 0:
                is_unclean = True
                break
        # 2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
        if is_unclean:
            d -= 1
            d %= 4
            nr = r + dr[d]
            nc = c + dc[d]

            while graph[nr][nc] != 0:
                d -= 1
                d %= 4
                nr = r + dr[d]
                nc = c + dc[d]
            q.append((nr, nc))

        # 3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
        else:
            # 한칸 후진용 임시 방향 temp_d
            temp_d = d
            temp_d += 2
            temp_d %= 4
            nr = r + dr[temp_d]
            nc = c + dc[temp_d]
            # 한 칸 후진할 수 있다면
            if graph[nr][nc] != 1:
                q.append((nr, nc))
            # 뒤쪽 칸이 벽이면 작동 멈추기
            else:
                return


q = deque([(R, C)])
clean(q)

answer = 0
for r in range(N):
    for c in range(M):
        if graph[r][c] == 2:
            answer += 1

print(answer)

그래프

프로그래머스 문제를 풀어 따로 게시물을 작성했다.