[백준]230213 문제풀이

11000. 강의실 배정

import sys
import heapq

N = int(sys.stdin.readline())
heap = []
clslst = []
cnt = 0
for i in range(N):
    a, b = map(int,sys.stdin.readline().split())
    heapq.heappush(clslst, (a, b))
for i in range(N):
    x = heapq.heappop(clslst)
    while heap and heap[0] <= x[0]:
        heapq.heappop(heap)
    heapq.heappush(heap, x[1])
    if len(heap) > cnt:
        cnt = len(heap)
print(cnt)

오늘의 리벤지. 이전에 그리디 문제로 만난적이 있어서 로직 자체는 어렵지 않게 생각했지만 힙에서 쓸 인덱스를 어떻게 할지가 관건이었던 문제. 시작시간과 종료시간을 힙으로 같이 넣은 다음에 현재 사용중인 강의실 힙에는 종료시간만 들어가서 힙에 들어갈 시작시간과 비교하는 식으로 풀어냈다.

1012. 유기농 배추

from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
T = int(input())
for i in range(T):
    M, N, K = map(int, input().split())
    land = [[0] * M for _ in range(N)]
    cab = []
    cnt = 0
    for i in range(K):
        a, b = map(int, input().split())
        cab.append((a, b))
        land[b][a] = 1

    while cab:
        cnt += 1
        a = cab.pop()
        queue = deque([a])
        while queue:
            node = queue.pop()
            for j in range(4):
                if (node[0] + dx[j], node[1] + dy[j]) in cab:
                    queue.appendleft((node[0] + dx[j], node[1] + dy[j]))
                    cab.remove((node[0] + dx[j], node[1] + dy[j]))

    print(cnt)

처음 제대로 풀어본 BFS 문제. DFS랑 다르게 while문이랑 deque만 적절히 잘 써주면 따로 고생하는 것 없이 간단하게 되는 것 같다.

10026. 적록색약

from collections import deque

N = int(input())
lst = []
for i in range(N):
    a = list(input())
    lst.append(a)
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
togo = []
for i in range(N):
    for j in range(N):
        togo.append((i,j))
visited = [[0] * N for _ in range(N)]
rgcnt = 0

while togo:
    x = togo.pop()
    queue = deque([x])
    rgcnt += 1
    while queue:
        node = queue.pop()
        visited[node[0]][node[1]] = 1
        for i in range(4):
            if (node[0]+dx[i], node[1]+dy[i]) in togo:
                if lst[node[0]][node[1]] == lst[node[0]+dx[i]][node[1]+dy[i]] == 'B':
                    queue.appendleft((node[0]+dx[i],node[1]+dy[i]))
                    togo.remove((node[0]+dx[i],node[1]+dy[i]))
                elif lst[x[0]][x[1]] != 'B' and lst[node[0]+dx[i]][node[1]+dy[i]] != 'B':
                    queue.appendleft((node[0]+dx[i],node[1]+dy[i]))
                    togo.remove((node[0] + dx[i], node[1] + dy[i]))

togo = []
for i in range(N):
    for j in range(N):
        togo.append((i,j))
visited = [[0] * N for _ in range(N)]
cnt = 0

while togo:
    x = togo.pop()
    queue = deque([x])
    cnt += 1
    while queue:
        node = queue.pop()
        visited[node[0]][node[1]] = 1
        for i in range(4):
            if (node[0]+dx[i], node[1]+dy[i]) in togo:
                if lst[node[0]][node[1]] == lst[node[0]+dx[i]][node[1]+dy[i]] == 'B':
                    queue.appendleft((node[0]+dx[i],node[1]+dy[i]))
                    togo.remove((node[0]+dx[i],node[1]+dy[i]))
                elif lst[node[0]][node[1]] == lst[node[0] + dx[i]][node[1] + dy[i]] == 'G':
                    queue.appendleft((node[0]+dx[i],node[1]+dy[i]))
                    togo.remove((node[0] + dx[i], node[1] + dy[i]))
                elif lst[node[0]][node[1]] == lst[node[0] + dx[i]][node[1] + dy[i]] == 'R':
                    queue.appendleft((node[0]+dx[i],node[1]+dy[i]))
                    togo.remove((node[0] + dx[i], node[1] + dy[i]))

print(cnt, rgcnt)

BFS 쉽다고 하자마자 귀신같이 개털린 문제... 짧은 시간에 급하게 푸느라 인덱스 정리도 로직 정리도 못해서 그냥 색약과 일반 카운트를 아예 따로 세버리는 식으로 해서 코드가 장황해졌다. 코드는 나중에 심심하면 정리해보는 걸로...