감시 (골드 4)

문제가 길어서 천천히 다 읽고 생각을 많이 하다가 입력 범위 보고 아 그냥 Brute-force로 풀어야겠다 싶어서 완전 탐색으로 풀었다.

1,2,3,4,5번 cctv의 특징을 나누어서 모든 경우의 수를 만들어 최소값을 선택했다.

from sys import stdin
import copy

rows, cols = map(int, stdin.readline().split())

matrix = [list(map(int, stdin.readline().split())) for _ in range(rows)]

hash_type = {
    1 : [0,1,2,3],
    2 : [(0,2), (1,3)],
    3 : [(0,1), (1,2), (2,3), (3,0)],
    4 : [(0,1,2), (1,2,3), (2,3,0), (3,0,1)],
    5 : [(0,1,2,3)]
}

hash_count = {
    1 : 4,
    2 : 2,
    3 : 4,
    4 : 4,
    5 : 1
}

fill = [(0,-1), (1,0), (0,1), (-1,0)]

def cctv(matrix, x, y, type_root):
    matrix_tmp = copy.deepcopy(matrix)
    type_num = matrix_tmp[x][y]
    
    type_ = hash_type[type_num]

    if type_num == 1:
        matrix_tmp = filler(matrix_tmp, x, y, type_root)
    else:
        for i in type_[type_root]:
            matrix_tmp = filler(matrix_tmp, x, y, i)
    return matrix_tmp
        
    
def filler(matrix, x, y, direction):
    dx, dy = fill[direction]
    
    while True:
        x += dx
        y += dy
        if 0 <= x < rows and 0 <= y < cols:
            if matrix[x][y] == 0:
                matrix[x][y] = 9
            elif matrix[x][y] == 6:
                break
        else:
            break
    return matrix


cctvs = []

for i in range(rows):
    for j in range(cols):
        if 1 <= matrix[i][j] <= 5:
            cctvs.append((i,j))

def check_zero(matrix):
    row = len(matrix)
    col = len(matrix[0])
    count = 0
    for r in range(row):
        for c in range(col):
            if matrix[r][c] == 0:
                count += 1
    return count

count_lst = []

def brute_force(cctvs, matrix):
    cctvs = copy.deepcopy(cctvs)
    if len(cctvs) == 0:
        count = check_zero(matrix)
        count_lst.append(count)
        return None

    cctv_item = cctvs.pop()
    x, y = cctv_item
    tmp_type = matrix[x][y]

    matrix_tmp = copy.deepcopy(matrix)

    for i in range(hash_count[tmp_type]):
        matrix = cctv(matrix_tmp, x, y, i)
        brute_force(cctvs, matrix)

cctvs.reverse()
brute_force(cctvs, matrix)
print(min(count_lst))

cctv 함수의 경우, 행열요소를 검사하고 해당 행열요소가 어떤 cctv타입인지 본 후 cctv가 체킹가능한 곳을 #으로 처리한 뒤 리턴해준다. 체킹방식은 cctv타입마다 여러개 존재할 수 있는데 이는 direction변수로 따로 처리했다.

brute_force 함수는 전체적인 과정을 담는 코드이며 재귀호출을 가진다. 재귀의 끝은 따로 cctv의 위치를 담은 cctvs 배열 변수의 길이가 0이되면 check_zero를 통해 사각지대의 수를 알아내고 종료한다.

filler함수는 cctv함수 내에서 사용되는 것인데, 단순하게 타입과 direction의 조합으로 matrix를 수정하는 역할이다.

이 코드에서 중요한 것은 "깊은 복사"이다. 만약 단순한 copy()로 복사한다면, 복사가 된 매트릭스나 배열을 수정할 경우 원본도 수정되기에 깊은 복사로 다른 메모리를 할당한 새로운, 동일한 형식의 매트릭스나 배열의 생성을 가능케 한다.

트럭 (실버 1)

하중문제라 대학 본전공때가 떠오르긴 했다. 단순하게 주어진대로 구현하면 된다. 트럭의 주어진 순서는 절대적이므로 time마다 트럭의 움직임을 다리의 하중규제에 따라 잘 조절해주면 된다. deque를 활용해서 풀었다.

from sys import stdin
from collections import deque

n, w, L = map(int, stdin.readline().split())
truck = list(map(int, stdin.readline().split()))

def next_step(deq, next_truck, L, time):
    used = False
    while not used:
        if sum(deq) + next_truck > L:
            deq.popleft()
            if sum(deq) + next_truck > L:
                deq.append(0)
                time += 1
                
            else:
                deq.append(next_truck)
                time += 1
                used = True
               
        else:
            deq.popleft()
            deq.append(next_truck)
            used = True
            time += 1
            
    return deq, used, time
    
def go_finish(deq, L, time):
    while sum(deq) > 0:
        deq.popleft()
        deq.append(0)
        time += 1
    return deq, time
    
deq = deque([0] * w)
time = 0
for t in truck:
    deq, used, time = next_step(deq, t, L, time)

deq, time = go_finish(deq, L, time)

print(time)

로봇청소기 (골드5)

구현문제, 문제의 조건의 루프구조를 잘 만들면 된다. 루프구조에 대한 힌트도 존재하는데, 1번으로 돌아간다를 잘 활용하면 된다.

from sys import stdin

rows, cols = map(int, stdin.readline().split())
start_x, start_y, direction = map(int, stdin.readline().split())

home_map = [list(map(int, stdin.readline().split())) for _ in range(rows)]

rotate = {0:3, 3:2, 2:1, 1:0}

move_direction = {
    0 : (-1,0),
    1 : (0,1),
    2 : (1,0),
    3 : (0,-1)
}

def robot_cleaning(home_map, start_x, start_y, direction):
    stop_sign = False
    robot_p = [start_x, start_y]

    while not stop_sign:

        if home_map[robot_p[0]][robot_p[1]] == 0:
            home_map[robot_p[0]][robot_p[1]] = 2
        next_lst = check_4_direction(robot_p[0], robot_p[1], home_map)
        # 주변에 청소되지 않은 곳이 있을 경우

        if len(next_lst) > 0:
            direction = rotate[direction]
            if 0 <= robot_p[0]+move_direction[direction][0] < rows and 0 <= robot_p[1]+move_direction[direction][1] < cols:
                if home_map[robot_p[0]+move_direction[direction][0]][robot_p[1]+move_direction[direction][1]] == 0:
                    robot_p = [robot_p[0]+move_direction[direction][0], robot_p[1]+move_direction[direction][1]]

        # 주변에 청소되지 않은 곳이 없을 경우
        else:
            if 0 <= robot_p[0] - move_direction[direction][0] < rows and 0 <= robot_p[1] - move_direction[direction][1] < cols:
                if home_map[robot_p[0] - move_direction[direction][0]][robot_p[1] - move_direction[direction][1]] == 0 | 2:
                    robot_p = [robot_p[0] - move_direction[direction][0], robot_p[1] - move_direction[direction][1]]

                else:
                    stop_sign = True
                    break
            else:
                stop_sign = True
                break

    return home_map


def check_4_direction(x,y,home_map):
    deltas = [(1,0),(-1,0),(0,1),(0,-1)]
    next_lst = []
    for d in deltas:
        if 0 <= x+d[0] < rows and 0 <= y+d[1] < cols:
            if home_map[x+d[0]][y+d[1]] == 0:
                next_lst.append((x+d[0], y+d[1]))
    return next_lst

after_map = robot_cleaning(home_map, start_x, start_y, direction)
count = 0
for i in range(rows):
    for j in range(cols):
        if after_map[i][j] == 2:
            count += 1

print(count)

4개의 방향을 확인하고 후보들을 리스트에 넣어서 리턴하는 함수 하나만 활용했고 나머지는 whiled안에 모두 코딩했다. 혹시몰라 stop_sign변수를 넣었는데 없어도 괜찮을 듯.

풀면서 두번 틀렸는데 이상한 실수를 발견하지 못 하고 있었다.

if home_map[robot_p[0] - 
move_direction[direction][0]][robot_p[1] - 
move_direction[direction][1]] == 0 | 2:

이 표현 이전에 0 or 2를 적었다. 실제로 둘다 틀리다.

특정한 계산 값 == 0 or 2는 == 와 or 즉 비교연산자 두개가 동시에 들어간다. 이럴땐 in (0,2)로 적어야하는데 여기를 틀린지 모르고 층층이 print해서 엄한 곳만 찾고 있었다.