우주의 IT 소행성

https://acmicpc.net/problem/11286 

절댓값과 일반값을 구분지어 저장하고, 

절댓값의 최소가 여러 개 있다면 그 일반값 중 최소를 출력하는 문제로

처음에는 deque와 람다 sorted 2중 정렬을 이용해 풀려고 했으나 시간 초과

시간 초과 코드

import sys
from collections import deque
input = sys.stdin.readline

a = deque()
for _ in range(int(input())):
    x = int(input())
    if x == 0:
        if len(a) == 0:
            print(0)
            continue
        a = deque(sorted(a, key=lambda q: (q[1], q[0])))
        print(a.popleft()[0])

    else:
        a.append((x, abs(x)))

10만이 넘는 배열 속에서 2^31의 최대 수를 정렬하려니 시간 초과.

파이썬 import heapq를 사용해서 절댓값을 뽑아주기로 했다.

import sys
import heapq
input = sys.stdin.readline

heap = []
for _ in range(int(input())):
    x = int(input())
    if x == 0:
        try:
            print(heapq.heappop(heap)[1])
        except:
            print(0)
        continue
    heapq.heappush(heap, (abs(x), x))

https://www.acmicp.net/problem/16946 

from collections import deque
n, m = map(int, input().split())
check = [[False] * m for _ in range(n)]
a = [list(map(int, list(input()))) for _ in range(n)]
group = [[0] * m for _ in range(n)]
group_size = []
group_number = 1
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs(n1, n2):
    queue = deque()
    queue.append((n1, n2))
    check[n1][n2] = True
    group[n1][n2] = group_number
    count = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if a[nx][ny] == 0 and not check[nx][ny]:
                    check[nx][ny] = True
                    queue.append((nx, ny))
                    group[nx][ny] = group_number
                    count += 1
    group_size.append(count)


for i in range(n):
    for j in range(m):
        if not check[i][j] and a[i][j] == 0:
            bfs(i, j)
            group_number += 1


for i in range(n):
    for j in range(m):
        if a[i][j] == 0:
            print(0, end='')
        else:
            near = set()
            for k in range(4):
                nx, ny = i + dx[k], j + dy[k]
                if 0 <= nx < n and 0 <= ny < m:
                    if a[nx][ny] == 0:
                        near.add(group[nx][ny])
            ans = 1
            for g in near:
                ans += group_size[g - 1]
            print(ans % 10, end='')
    print()

일단 맨 처음 빈 칸을 모두 그룹지어 그 개수를 구해줌.

벽을 비웠을 때 인접한 칸이 미리 만들어 둔 빈 칸 그룹에 포함된다면

그 그룹의 수 + 자기 자신을 더해주면 되는데

bfs는 한번만 돌려주면 됨(처음 빈칸을 그룹 지을때)

그 뒤 matrix에서 벽인 부분만을 찾아 인접 4칸을 순회하며

첫 bfs에서 지정해 둔 그룹인지만 파악해주고

그룹이라면  그 그룹의 수를 더해줌.

https://www.acmicpc.net/problem/14502 

n, m = map(int, input().split())
data = [] # 초기 맵
temp = [[0] * m for _ in range(n)] # 벽을 설치한 맵

for _ in range(n):
    data.append(list(map(int, input().split())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
result = 0

def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                virus(nx, ny)

def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score


def dfs(count):
    global result
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        result = max(result, get_score())
        return

    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1

dfs(0)
print(result)

https://www.acmicp.net/problem/16948 

from collections import deque
n = int(input())
a = [[False] * (n + 1) for _ in range(n + 1)]
r1, c1, r2, c2 = map(int, input().split())
dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]

queue = deque()
queue.append((r1, c1, 0))
while queue:
    x, y, count = queue.popleft()
    a[x][y] = True
    if (x, y) == (r2, c2):
        print(count)
        exit()

    for i in range(6):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and not a[nx][ny]:
            queue.append((nx, ny, count + 1))
            a[nx][ny] = True

print(-1)

이동경로가 많아졌을 뿐, bfs의 큰 틀에서 벗어나진 않은 문제.

count 가중치를 같이 queue에 넣고 돌려 목표점에 도달했을 때 count를 반환해주면 됨.

반환에 실패했을 경우 -1 출력.