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)

• 이미지를 공유하는 방법

이미지를 공유하는 방법에는 2가지가 있다.

1. Dockerfile을 공유한다.

2. 빌드된 이미지를 공유한다.

1번의 방법을 사용하면 받아온 후에 빌드를 해야하지만, 2번을 사용하면 빌드된 이미지를 공유하기 때문에 빌드를 할 필요도 없다.

• DockerHub에 이미지를 push하기

 도커허브에 업로드 하는 방법과 개인 저장소에 업로드 하는 방법이 있지만, 우선은 도커허브에 업로드하는 방법을 사용해보도록 하자.

DockerHub에 계정을 만들고 리포지토리도 생성한다.

그리고는 로컬에 와서 push 해주도록 한다.

깃과 마찬가지로

docker push {이미지 이름}

이렇게 사용하지만, {레포지토리 이름/이미지 이름:태그}의 이름으로 이미지가 생성되어 있어야 한다.

물론 이것이 개인 계정이기 때문에 docker login을 해야 할 수도 있다.

docker login

해당 명령어를 이용하여 계정과 비밀번호를 입력해주면 로그인이 완료된다.

이렇게 새로운 이미지가 올라간 것을 볼 수 있다.

• DockerHub에서 이미지를 pull하기

push와 반대로 올라간 이미지를 pull 할 수 있다.

docker pull {리포지토리 이름/이미지 이름:태그}

해당 명령어로 가져오면 된다.

이렇게 pull을 하면 새로운 이미지가 생성되어 있는 것을 볼 수 있다.

• 컨테이너의 중지와 재시작

docker ps

docker ps를 입력하면 현재 실행 중인 도커 컨테이너들을 확인할 수 있다.

만약 현재 실행 중인 컨테이너 외에도 중지된 컨테이너까지 확인하기 위해서는 다음 명령어를 사용하면 된다.

docker ps -a

이러면 현재 종료되어 있는 컨테이너도 확인할 수 있다.

이 종료되어 있는 컨테이너를 다시 재시작할 수도 있다.

docker run은 이미지를 기반으로 새 컨테이너를 만들지만, 변경사항이 없어서 컨테이너를 재실행하고 싶다면 docker ps -a로 컨테이너를 검색한 후

docker start {container ID || container name}

이렇게 종료된 컨테이너를 재실행한 것을 볼 수 있다.

• Attached, Detached

방금 해보았던 docker start로 컨테이너를 실행하면, 외부에서 docker ps로 상태만 확인할 수 있었고 내부에서 작업은 하지 않았었다.

분명히 실행 중인데도 말이다.

이 전의 docker run으로 컨테이너를 실행하면, 해당 터미널에서 컨테이너가 실행되고 다른 터미널에서 상태를 확인할 수 있었다.

이제 여기서 자유롭게 attached, detached를 설정하여 작업해 보도록 하자.

우선 docker start는 detached 모드가 디폴트이며, docker run은 attached 모드가 디폴트이다.

docker run을 확인해보자.

이렇게 콘솔에 컨테이너의 결과가 출력되는 것을 볼 수 있다.

이 컨테이너를 콘솔과 연결되지 않는 detached 모드로 실행하기 위해서는, -d 옵션을 넣어주면 된다.

이렇게 -d 옵션을 넣어주면, 이전과는 다르게 바로 컨테이너가 실행되었다고 나오고 터미널과는 분리되는 것을 볼 수 있다.

분리된 컨테이너와 터미널을 다시 연결하고 싶다면, attach 명령어를 사용하면 된다.

docker attach {container ID || container name}

이렇게 다시 연결되어 결과가 출력되는 것을 볼 수 있다.

터미널과 연결시키지 않고 로그만 가져오고 싶다면, logs 명령어를 사용하면 된다.

이렇게 바로 출력의 결과만 가져오는 것을 볼 수 있다.

• 인터렉티브 모드로 작업하기

웹서버뿐만 아니라 짠 코드를 직접 실행시킬 수도 있다.

작성한 파이썬 코드를 실행해보도록 하겠다.

Dockerfile은 다음과 같이 작성했다.

FROM python

WORKDIR /python

COPY . /python

CMD ["python", "rng.py"]

해당 Dockerfile을 바탕으로 이미지를 생성하고, 컨테이너를 실행한다.

그리고는 run -it를 사용하여, 인터렉티브하게 컨테이너를 실행한다.

docker run -it {image ID || image name}

이러면 해당 컨테이너와 상호작용하며 실행할 수 있다.

run이 아닌 start의 상황에서는 -ai 옵션을 사용하여 인터렉티브하게 재실행한다.

• 이미지와 컨테이너 삭제하기

그 동안 생성했던 많은 이미지와 컨테이너들을 삭제해보도록 하자.

컨테이너를 제거할 때는 rm 명령어를 사용한다.

docker rm {container ID || container name}

당연히 실행 중인 컨테이너는 삭제할 수 없고, 현재 종료된 컨테이너만 제거가 가능하다.

이번에는 이미지를 삭제해보자.

이미지를 삭제할 때는 rmi 명령어를 사용한다.

docker rmi {image ID || image name}

이렇게 이미지가 삭제되는 것을 볼 수 있다.

여기서도 이미지는 해당 이미지를 사용하여 실행 중인 컨테이너가 존재하지 않을 때만 삭제가 가능하다.

해당 명령어를 사용하면, 삭제 가능한 모든 이미를 삭제한다.

docker image prune

만약 컨테이너를 종료 후 해당 컨테이너를 자동으로 제거하고 싶다면, run을 하면서 --rm 옵션을 넣어주면 된다.

docker run --rm {image ID || image name}

이렇게 종료하자마자 자동으로 삭제되는 것을 볼 수 있다.

• 컨테이너에서의 파일 복사

실행 중인 컨테이너로 또는 실행 중인 컨테이너 밖으로 파일 또는 폴더를 복사할 수 있다.

해당 과정에서는 cp 명령어를 사용한다.

docker cp {복사하려는 파일 혹은 폴더} {container name}:{복사하려는 경로}

당연히 반대로 컨테이너에서 가져올 수도 있다.

cp 명령어를 사용하여 경로의 순서를 바꾸면 된다.

docker cp {container name}:{복사하려는 경로} {복사하려는 파일 혹은 폴더}

• 컨테이너와 이미지에 이름 혹은 태그 지정하기

지금까지는 자동으로 도커에서 생성된 이름만을 사용했다.

당연히 이런 이름들도 우리가 직접 지정할 수 있다.

직접 지정하는 방법을 알아보도록 하자.

--name 옵션에 이름을 지정해주면 된다.

docker run --name {container name} {image ID || image name}

myapp이라는 이름이 지정된 것을 볼 수 있다.

이번에는 이미지에 이름을 지정해보자.

이미지의 이름을 태그라고 하며 2개로 구분할 수 있다.

이미지의 리포지토리 : 이미지의 태그 이렇게 구성이 되어 있는 데, 이렇게 만든 이유는 여러개의 특정화된 이미지 그룹을 만들 수 있기 때문이다.

이미지를 가져올 때도 태그를 지정할 수 있으며, 보통은 특정 버전의 이미지를 가져올 때 사용한다.

이미지의 이름을 생성할 때는 -t 옵션을 사용한다.

docker build -t {이미지의 이름}:{이미지의 태그} .

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)