100년 뒤 개발자 한승규입니다.

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

우선 한 단계씩 퍼져나가야 하기 때문에 BFS를 사용했다.

우선 익은 토마토들의 위치를 가져와야 하기 때문에 반복문을 사용하여 1인 토마토의 위치를 가져온다.

여기서 처음에는 리스트를 사용했었는 데, 시간 초과가 발생한다.

deque를 사용하는 것을 추천한다.

익은 토마토들을 저장할 때 ripe이라는 deque를 사용했는 데, 여기에는 익은 토마토의 위치 뿐만 아니라 지난 날짜까지 저장을 해준다.

이렇게 현재 날짜를 저장해주어야 다음 차례에 날짜를 +1해가며 BFS를 진행할 수 있기 때문이다.

익은 토마토로 부터 4방향을 탐색하고 안 익은 토마토가 있다면, 해당 토마토에 날짜 +1 한 정보와 위치를 ripe deque에 추가해준다.

그리고는 ripe가 남아 있을 동안 반복문을 진행하고 만약 while로 모든 ripe를 탐색한 후에도 0인 토마토가 남아있다면 -1을 출력하며, 아니라면 가지고 있던 max_result를 출력해준다.

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

ripe = deque()

for m in range(M):
    for n in range(N):
        if tomato[m][n] == 1:
            ripe.append([0, m, n])

max_result = 0

while ripe:

    cur_cnt, cur_m, cur_n = ripe.popleft()

    max_result = max(max_result, cur_cnt)

    for next_m, next_n in [[cur_m, cur_n + 1], [cur_m, cur_n - 1], [cur_m + 1, cur_n], [cur_m - 1, cur_n]]:
        if 0 <= next_m < M and 0 <= next_n < N and tomato[next_m][next_n] == 0:
            tomato[next_m][next_n] = 1
            ripe.append([cur_cnt + 1, next_m, next_n])


is_finish = True

for m in range(M):
    for n in range(N):
        if tomato[m][n] == 0:
            is_finish = False
            break
    if not is_finish:
        break

print(max_result if is_finish else -1)

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

물의 높이를 올려가며 해당 높이에 대하여 그래프의 탐색을 진행했다.

한 번 틀렸었는데, 높이가 0일 때도 고려를 해야 한다.

import sys

N = int(sys.stdin.readline())

land = list()

for _ in range(N):
    land.append(list(map(int, sys.stdin.readline().split())))

max_result = 0

for height in range(101):
    result = 0

    visited = [[False for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for t in range(N):
            if visited[i][t] is False and land[i][t] > height:
                visited[i][t] = True
                need_visit = [[i, t]]

                result += 1

                while need_visit:
                    cur_i, cur_t = need_visit.pop()

                    for next_i, next_t in [[cur_i + 1, cur_t], [cur_i - 1, cur_t], [cur_i, cur_t + 1], [cur_i, cur_t - 1]]:
                        if 0 <= next_i < N and 0 <= next_t < N and not visited[next_i][next_t] and land[next_i][next_t] > height:
                            need_visit.append([next_i, next_t])
                            visited[next_i][next_t] = True

    max_result = max(max_result, result)

print(max_result)

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

해당 문제도 평범한 그래프 문제이다.

visited 배열로 방문을 기록할 수 있도록 하였다.

import sys

for _ in range(int(sys.stdin.readline().strip())):

    M, N, K = map(int, sys.stdin.readline().split())

    land = [[0 for _ in range(M)] for _ in range(N)]

    for _ in range(K):
        m, n = map(int, sys.stdin.readline().split())
        land[n][m] = 1

    result = 0

    visited = [[False for _ in range(M)] for _ in range(N)]

    for n in range(N):
        for m in range(M):
            if visited[n][m] or land[n][m] == 0:
                continue

            result += 1

            need_visit = [[n, m]]
            visited[n][m] = False

            while need_visit:

                cur_n, cur_m = need_visit.pop()

                for next_n, next_m in [[cur_n, cur_m + 1], [cur_n, cur_m - 1], [cur_n + 1, cur_m], [cur_n - 1, cur_m]]:
                    if 0 <= next_n < N and 0 <= next_m < M:
                        if land[next_n][next_m] == 1 and visited[next_n][next_m] is False:
                            need_visit.append([next_n, next_m])
                            visited[next_n][next_m] = True
    print(result)

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

전형적인 그래프 탐색 문제이다.

BFS로 풀든, DFS로 풀든 상관 없을 것이라고 생각한다.

visited 배열을 만들어 방문했던 기록을 남기고, 만약 방문했던 곳이라면 해당 지역은 건너뛸 수 있도록 했다.

그리고 항상 그래프를 탐색할 때에는 구역 내에 있는 지 확인을 먼저 하고 진행할 수 있도록 했다.

만약 땅이 맞다면, 방문을 한다는 의미로 visited를 True로 바꾸고 다음에 방문을 진행할 need_visit 배열에 추가하도록 했다.

import sys

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

while True:

    w, h = map(int, sys.stdin.readline().split())

    if w == 0 and h == 0:
        break

    land = list()
    visited = [[False for _ in range(w)] for _ in range(h)]

    result = 0

    for _ in range(h):
        land.append(list(map(int, sys.stdin.readline().split())))

    for height in range(h):
        for width in range(w):

            if visited[height][width] is True:
                continue

            if land[height][width] == 0:
                visited[height][width] = True
                continue

            result += 1

            need_visit = [[height, width]]
            visited[height][width] = True

            while need_visit:
                cur_height, cur_width = need_visit.pop(0)

                for i in range(8):
                    target_height, target_width = cur_height + dy[i], cur_width + dx[i]
                    if 0 <= target_height < h and 0 <= target_width < w and land[target_height][target_width] == 1 and not visited[target_height][target_width]:
                        need_visit.append([target_height, target_width])
                        visited[target_height][target_width] = True

    print(result)

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

당연히 고민하지 않고 BFS로 풀었다.

지나온 길을 기록하기 위해 N x M 크기의 visited 배열을 사용했다.

import sys

N, M = map(int, sys.stdin.readline().split())

miro = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
visited = [[float('inf') for _ in range(M)] for _ in range(N)]

bfs = [[0, 0, 0]]

result = -1

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

while bfs:
    count, x, y = bfs.pop(0)

    if x == N - 1 and y == M - 1:
        result = count
        break

    for i in range(4):
        if 0 <= x + dx[i] < N and 0 <= y + dy[i] < M and miro[x + dx[i]][y + dy[i]] == 1 and visited[x + dx[i]][y + dy[i]] > count + 1:
            bfs.append([count + 1, x + dx[i], y + dy[i]])
            visited[x + dx[i]][y + dy[i]] = count + 1


print(result + 1)

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

단순한 그래프 문제이다.

입력받은 edge를 배열에 저장하고 해당 배열을 DFS, BFS에 맞게 탐색하면서 풀었다.

DFS, BFS에서의 다른 점은 BFS는 바로바로 다음 방문 배열에 넣은 반면, DFS는 해당 노드에서 인접한 노드를 모두 구해 배열로 만든 후 다음 방문 배열 앞으로 넣어주었다.

import sys

N, M, V = map(int, sys.stdin.readline().split())

graph = [[False for _ in range(N+1)] for _ in range(N+1)]

for i in range(M):
    V1, V2 = map(int, sys.stdin.readline().split())
    graph[V1-1][V2-1] = True
    graph[V2-1][V1-1] = True

DFS, BFS = [False for i in range(N)], [False for i in range(N)]
to_visit = [V-1]

while to_visit:
    cur_node = to_visit.pop(0)
    if DFS[cur_node]:
        continue
    save_to_visit = []
    for i in range(N):
        if graph[cur_node][i] and not DFS[i]:
            save_to_visit.append(i)

    to_visit = save_to_visit + to_visit

    print(cur_node + 1, end=' ')
    DFS[cur_node] = True

print()

to_visit = [V-1]

while to_visit:
    cur_node = to_visit.pop(0)
    if BFS[cur_node]:
        continue

    for i in range(N):
        if graph[cur_node][i] and not BFS[i]:
            to_visit.append(i)

    print(cur_node + 1, end=' ')
    BFS[cur_node] = True

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

당연히 heap을 사용해야 한다는 것은 알고 있었지만, 어떻게 사용할 지에 대해서 고민을 많이 했었다.

보석과 가방을 같은 heap에 넣는다는 생각을 하는 게 좀 힘들었던 것 같다.

무게를 기준으로 최소 heap에 보석과 가방을 넣어준다.

가방 같은 경우는 같은 무게에서 가장 뒤로 갈 수 있도록 가치에는 무한을 넣어준다.

하나씩 꺼낼 때 쓸 heap도 만들어준다.

보석과 가방을 넣은 heap에서 하나씩 꺼내어서 반복문을 실행해준다.

만약 꺼낸 것이 보석이라면 최대 heap에 가치를 넣어준다.

만약 꺼낸 것이 가방이라면 최대 heap에서 하나의 보석을 넣을 수 있는 것이므로 가장 큰 값을 가져와 결과값에 더해준다.

그렇게해서 구한 결과값을 출력해주면 된다.

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())

jewelry = list()

for _ in range(N):
    heapq.heappush(jewelry, list(map(int, sys.stdin.readline().split())))

for _ in range(K):
    heapq.heappush(jewelry, [int(sys.stdin.readline().strip()), float('inf')])

result = 0
cur_jewelry = list()

while jewelry:

    weight, value = heapq.heappop(jewelry)

    if value == float('inf'):
        if cur_jewelry:
            result += heapq.heappop(cur_jewelry)
    else:
        heapq.heappush(cur_jewelry, value * -1)


print(result * -1)

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

당연히 회의실 문제랑 똑같은 줄 알고 heap으로만 바꿔서 풀었었다.

문제를 똑바로 읽지 않은 내 잘못이다..

이번 문제는 해당 강의를 모두 가능하도록 만들어야 한다.

그렇기에 끝나는 시간으로 정렬하는 것이 아닌, 시작하는 순서대로 해서 빨리빨리 받아서 끝내도록 해야한다.

나중에 퀵정렬을 사용하는 것이 아니라 heap을 사용하여 입력을 받았다.

강의실을 배정할 때도 가장 빨리 끝나는 시간 순으로 정렬을 해두고, 앞의 시간이랑 비교해서 만약 강의 진행이 불가능 하다면 새로운 강의실을 편성한다.

만약 가능하다면 해당 강의실의 끝나는 시간을 현재 강의가 끝나는 시간으로 변경한 후 다시 heap으로 넣어준다.

import sys
import heapq

heap = []

N = int(sys.stdin.readline().strip())

for i in range(N):
    S, T = map(int, sys.stdin.readline().split())

    heapq.heappush(heap, [S, T])

room = list()
heapq.heappush(room, heap[0][1])
heapq.heappop(heap)

while heap:
    heap_S, heap_T = heapq.heappop(heap)

    if room[0] <= heap_S:
        heapq.heappush(room, heap_T)
        heapq.heappop(room)
    else:
        heapq.heappush(room, heap_T)


print(len(room))

마지막에는 강의실의 개수를 출력하고 마무리 해준다.