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

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

구현 과정이 굉장히 어려웠던 문제이다.

우선 처음에 정보를 입력받고 바로 반복문으로 현재 비버의 위치, 목적지, 물의 위치를 각각 배열과 변수에 저장하였다.

그 후에는 당연히 BFS를 진행하였다.

한 턴이 반복 될 때마다 우선 물을 이동시킨다.

. 인 영역이면 물을 전파시켰고, 만약 전파가 되었다면 임시로 만든 deque에 저장하였으며 다음 턴에도 물의 전파를 위해 해당 턴이 끝나면 water deque에 임시 deque를 대입해주었다.

물의 전파가 끝나면 해당 턴에서 다시 비버를 이동시켜야 한다.

당연히 중복을 제거하기 위해 visited 배열을 사용했다.

deque에서 가능한 현재 비버의 위치를 가져왔으며, 만약 해당 위치가 목적지라면 반복문을 탈출 할 수 있도록 하였다.

비버의 위치를 가져온 후에는 4번의 반복을 통해 4 방향으로 이동시켜본 후 만약 해당 위치가 .이거나 목적지라면 visited = True로 바꾸어주고 다음 비버가 이동하기 위해 만든 next_move deque에 넣어준다.

이렇게 move에 데이터가 남아있을 동안 반복하고 모두 반복을 해도 도착하지 못하면 KAKTUS를 출력, 도착 했다면 결과를 출력하면 된다.

import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

result = 0

move = deque()
water = deque()

target_r, target_c = -1, -1

arrive = False

forest = [list(sys.stdin.readline().strip()) for _ in range(R)]

for r in range(R):
    for c in range(C):
        if forest[r][c] == 'S':
            move.append([r, c])
            forest[r][c] = '.'
        elif forest[r][c] == 'D':
            target_r, target_c = r, c
        elif forest[r][c] == '*':
            water.append([r, c])


while move:

    # 물 먼저 이동
    next_water = deque()

    while water:

        cur_r, cur_c = water.popleft()

        for next_r, next_c in [[cur_r, cur_c - 1], [cur_r, cur_c + 1], [cur_r - 1, cur_c], [cur_r + 1, cur_c]]:
            if 0 <= next_r < R and 0 <= next_c < C and forest[next_r][next_c] == '.':
                forest[next_r][next_c] = '*'
                next_water.append([next_r, next_c])

    water = next_water

    # 비버 이동 가능 한 곳으로 이동

    next_move = deque()

    visited = [[False for _ in range(C)] for _ in range(R)]

    while move:

        cur_r, cur_c = move.popleft()

        if cur_r == target_r and cur_c == target_c:
            arrive = True
            break

        for next_r, next_c in [[cur_r, cur_c - 1], [cur_r, cur_c + 1], [cur_r - 1, cur_c], [cur_r + 1, cur_c]]:
            if 0 <= next_r < R and 0 <= next_c < C and (forest[next_r][next_c] == '.' or forest[next_r][next_c] == 'D') and visited[next_r][next_c] is False:
                next_move.append([next_r, next_c])
                visited[next_r][next_c] = True

    move = next_move

    if arrive:
        break

    result += 1

print(result if arrive else 'KAKTUS')

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