🔥 TIL - Day 37

이 문제는 기억하자 !!

📌 샤오미 로봇 청소기

2차원의 공간이 주어졌을 때 로봇청소기가 한 번의 동작으로 청소할 수 있는 범위의 수를 구하여라.

• 0 은 청소되지 않은 공간 (청소를 필요로 하는 공간)
• 1은 벽

이동조건

• 왼쪽방향부터 왼쪽방향으로 청소공간 탐색
• 동,서,남,북 모두 청소할 수 없다면 현재 방향을 바라보고 반대방향으로 한 칸 이동
• 동,서,남,북 모두 청소 불가능하고 반대방향이 벽이라면 동작종료

입력은 시작위치 x,y좌표와 방향이 주어진다.

방향

• 북: 0
• 동: 1
• 남: 2
• 서: 3

처음에는 평범한 BFS 인줄 알았는데 중간중간 고려해야 되는 게 너무 많았다 ㅠㅠ

뽀인트 1
이동좌표를 아래와 같이 구성했을 때 각 위치에서 왼쪽으로 회전할 수 있는 메서드

#     북  동  남  서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

# 북 -> 서: 0 -> 3
# 동 -> 북: 1 -> 0
# 남 -> 동: 2 -> 1
# 서 -> 남: 3 -> 2
def rotate(d):
    return (d + 3) % 4

뽀인트2
반대방향으로 한 칸 이동할 수 있는 메서드

# 북 -> 남: 0 -> 2
# 동 -> 서: 1 -> 3
# 남 -> 북: 2 -> 0
# 서 -> 동: 3 -> 1
def goback(d):
    return (d + 2) % 4

BFS에서 회전같은 것들이 나오면 많이 어렵게 느껴지곤 했는데 좋은 풀이법을 하나 배워간다 ㅎ (나머지 연산 !!!!!!!!!!!!!!!!!!!!!!!!!)

전체코드

current_r, current_c, current_d = 7, 4, 0
current_room_map = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
#    북,동,남,서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

# 왼쪽 회전 메서드
# 북 -> 서 0 -> 3
# 동 -> 북 1 -> 0
# 남 -> 서 2 -> 3
# 서 ->남  3 -> 2
def rotate(d):
    return (d + 3) % 4

# 현재 방향 기준 반대쪽 방향으로 이동하는 메서드
# 북 -> 남 0 -> 2
# 동 -> 서 1 -> 3
# 남 -> 북 2 -> 0
# 서 -> 동 3 -> 1
def go_back(d):
    return (d+2) % 4


def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
    n = len(room_map)
    m = len(room_map[0])
    res = 0
    if room_map[r][c] == 0:
        res += 1
        room_map[r][c] = -1
    q = [(r,c,d)]

    while q:
        r, c, d = q.pop(0)
        d_idx = d
        for i in range(4):
            d_idx = rotate(d_idx)

            nr = r + dr[d_idx]
            nc = c + dc[d_idx]

            if 0 <= nr < n and 0 <= nc < m and room_map[nr][nc] == 0:
                room_map[nr][nc] = -1
                q.append((nr, nc, d_idx))
                res += 1
                break # break를 해주지 않으면 4방향 중 청소 가능한 영역이 있음에도 반복문의 마지막에서 청소불가능이고 뒷쪽도 막혀있다면 종료되어버림

            elif i == 3: # 4번째 방향 탐색시(마지막 탐색) 위 if문에 걸리지 않았다면 청소가능한 지역이 아니라는 것이므로 뒤쪽 이동한다 (방향유지)
                d_idx = go_back(d)
                nr = r + dr[d_idx]
                nc = c + dc[d_idx]
                q.append((nr, nc, d))

                if room_map[nr][nc] == 1: # 뒤쪽방향이 벽으로 막힌 경우
                    return res

    return res


# 57 가 출력되어야 합니다!
print(get_count_of_departments_cleaned_by_robot_vacuum(current_r, current_c, current_d, current_room_map))

📌 백준 2609 최대공약수와 최소공배수

코테에 이런 문제가 잘 나오진 않겠지만 호오오오옥시나 나왔을 때 못 풀면 너무 창피하니까 ...

최대공약수? ➡️ 유클리드 호제법!!

유클리드 호제법

• a가 b보다 클 때, a를 b로 나눈 나머지가 0인 경우 b가 a와 b의 최대공약수이다.
• 재귀로 구현 가능 (재귀가 되니까 당연히 반복문도 됨!)

def get_gcd(a, b):
    if b == 0: 
        return a

    return get_gcd(b, a % b)

최소공배수? ➡️ (두 수의 곱) / 최대공약수

print((a*b)//gcd)

전체코드

def get_gcd(a, b):
    if b == 0:
        return a

    return get_gcd(b, a % b)


a, b = map(int, input().split())
gcd = get_gcd(a, b)
print(gcd)
print((a*b)//gcd)

📌 백준 2805 나무 자르기

값을 가지고 하는 이분탐색
보통 이분탐색을 사용하는 많은 문제들이 정렬된 리스트의 중간값을 잡고 한 쪽으로 탐색 영역을 줄여가는 방식인데 이번 문제는 리스트가 아닌 특정 값을 가지고 이분탐색을 했다. (이것도 보통인가 .. ?)

목재절단기의 높이 (mid)를 최대값 쪽 혹은 최소값 쪽으로 줄여가며 탐색한다.

n, m = map(int, input().split())
trees = list(map(int, input().split()))

# minh: 1 (나무의 최소높이는 1)
# maxh: 현재 나무 중 최고높이
minh, maxh = 1, max(trees)

while minh <= maxh:
    mid = (minh + maxh) // 2 # 목재절단기의 높이
    tmp = 0 # 벌목되는 나무들의 길이의 합

    for t in trees:
        if t > mid: # 벌목되는 높이에 해당하는 나무만 벌모되도록
            tmp = tmp + (t - mid)

    # mid의 높이로 벌목한 결과 목표로 한 길이보다 큰 경우
    if tmp >= m:
        minh = mid + 1 # 최소값을 중간값+1로 갱신해서 더 높은 높이에서 벌목되어 더 작은 길이가 벌목되도록 한다.
    else:
        maxh = mid - 1 # 최대값을 중간값+1로 갱신해서 더 낮은 높이에서 벌목되어 더 큰 길이가 벌목되도록 한다.

print(maxh)