[TIL_Carrotww] 121 - 23/06/14

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 로봇 청소기

bfs 문제이지만 사실상 문제에서 하라는대로 하면 풀리는 시뮬레이션이다.
문제에서 하라는대로 하지 않고 풀다가 시간이 좀 걸렸다 ㅠ

시계 반대방향으로 도는것도 직접 만들어줬는데 함수로 만들걸 그랬다.

• 풀이

def solve():
    import sys
    from collections import deque

    n, m = map(int, sys.stdin.readline().split())
    r, c, d = map(int, sys.stdin.readline().split())

    # d -> 0 북, 1 동, 2 남, 3 서
    graph = []
    for _ in range(n):
        graph.append(list(map(int, sys.stdin.readline().split())))
    visited = [[0]*m for _ in range(n)]
    queue = deque()
    direct = [[(0, -1, 3), (1, 0, 2), (0, 1, 1), (-1, 0, 0)], 
              [(-1, 0, 0), (0, -1, 3), (1, 0, 2), (0, 1, 1)],
              [(0, 1, 1), (-1, 0, 0), (0, -1, 3), (1, 0, 2)],
              [(1, 0, 2), (0, 1, 1), (-1, 0, 0), (0, -1, 3)]]
    back_direct = [(1, 0), (0, -1), (-1, 0), (0, 1)]
    queue.append([r, c, d, 1])
    visited[r][c] = 1

    while queue:
        cur_r, cur_c, cur_d, cnt = queue.popleft()
        if visited[cur_r][cur_c] == 0:
            visited[cur_r][cur_c] = 1
            cnt += 1
        is_go = False
        for rr, cc, dd in direct[cur_d]:
            n_r, n_c = cur_r+rr, cur_c+cc
            n_d = dd
            if (n_r >= 0 and n_r < n) and (n_c >= 0 and n_c < m) and graph[n_r][n_c] == 0 and visited[n_r][n_c] == 0:
                is_go = True
                break
        if is_go:
            queue.append([n_r, n_c, n_d, cnt])
        else:
            rr, cc = back_direct[cur_d]
            n_r, n_c = cur_r+rr, cur_c+cc
            if (n_r < 0 or n_r >= n) or (n_c < 0 or n_c >= m) or graph[n_r][n_c] == 1:
                print(cnt)
                return
            queue.append([n_r, n_c, cur_d, cnt])

if __name__ == "__main__":
    solve()

direct -> 첫번째 인덱스부터 네 번째 인덱스까지가 북 동 남 서 를 바라보고 있을때 각각 시계 반대방향으로 전환하는걸 나타낸 것이다.
얼마 안될거같아서 그냥 썼는데 함수로 빼놓는것도 좋을 것 같다.
back_direct -> 갈곳이 없을때 뒤로 움직이는 리스트를 만들었다. 순서는 같다.

코딩테스트 스터디에서 풀었던 문제인데 bfs로 슈루룩 풀면 풀리나? 하면서 시작을 이상하게 해서 풀이 시간이 너무 길어진 문제다. 한시간 가까이 쓴듯...
이렇게 생각할 필요 없는 문제는 그냥 20분컷 해야하는데..ㅎ

🔍 백준 강의실 배정

우선순위 큐 문제이다 heapq를 써야겠다고만 떠올리면 된다.

def solve():
    import sys
    import heapq
    N = int(sys.stdin.readline())

    lecture = []
    for _ in range(N):
        start, end = map(int, sys.stdin.readline().split())
        lecture.append([start, end])

    lecture.sort()
    heap = [lecture[0][1]]

    for i in range(1, N):
        lecture_start_time, lecture_end_time = lecture[i][0], lecture[i][1]
        if lecture_start_time < heap[0]:
            heapq.heappush(heap, lecture_end_time)
        else:
            heapq.heappop(heap)
            heapq.heappush(heap, lecture_end_time)

    print(len(heap))

if __name__ == "__main__":
    solve()