IT-garden

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque

m,n,h=map(int,input().split())
a=[[list(map(int,input().split())) for i in range(n)] for depth in range(h)]

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

def bfs():
    while de:
        z,x,y=de.popleft()
    
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h:
                if a[nz][nx][ny] == 0:
                    a[nz][nx][ny] = a[z][x][y] + 1
                    de.append([nz, nx, ny])

de=deque()
for i in range(h):
    for j in range(n):
        for k in range(m):
            if a[i][j][k] == 1:
                de.append([i, j, k])

bfs()

z= 1
result = -1

for i in a:
    for j in i:
        for k in j:
            if k == 0:
                z = 0

            result=max(result,k)

if z == 0: #모두 익지 못한 상태
    print(-1)
elif result == 1: #모두 익어있던 상태 
    print(0)
else:
    print(result-1)

백준 알고리즘 7569번 : www.acmicpc.net/problem/7569

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

정답

from collections import deque
import copy

n=int(input())
a=[list(map(int,input().split())) for i in range(n)]

c=1
ch=copy.deepcopy(a)
r=1e9

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

def bfs(s1,s2,c1):
    de=deque()
    de.append([s1,s2])
   
    while de:
        x,y=de.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if ch[nx][ny] == 1:
                    ch[nx][ny] = c1
                    de.append([nx,ny])

for i in range(n): #육지들을 숫자로 나눠주기
        for j in range(n):
            if ch[i][j] == 1:
                c += 1
                ch[i][j] = c
                bfs(i,j,c)

def bfs2(s):
    global r
    dist=[[-1]*n for i in range(n)] 
    de=deque()

    for i in range(n):
        for j in range(n):
            if ch[i][j] == s:
                de.append([i,j])
                dist[i][j] = 0

    while de:
        x,y=de.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if ch[nx][ny] != 0 and ch[nx][ny] != s: #다른 육지에 닿은 경우
                    r = min(r,dist[x][y])
                    return
                
                if ch[nx][ny] == 0 and dist[nx][ny] == -1: 
                    dist[nx][ny] =dist[x][y] + 1
                    de.append([nx,ny])

for i in range(2,c+1): #육지의 수
    bfs2(i)

print(r)

0인 것을 n개 뽑아 조합시켜서 BFS를 적용해 계산하였더니 시간초과가 나왔습니다.

정답 방식은 육지들을 숫자로 나눠주었습니다. (bfs 함수 이용)

그리고 육지와 육지 사이의 거리는 BFS를 이용해 계산하였고 다른 육지를 만난 경우 더 적은 거리를 r에 담아 출력했습니다. (bfs2 함수 이용)

백준 알고리즘 2146번 : www.acmicpc.net/problem/2146

문제

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque

f, s, g, u, d=map(int,input().split())

a=[-1]*(f+1)
dx=[u,-d]

def bfs(g,s):
    de=deque()
    de.append(s)
    a[s]=0
    
    while de:
        x=de.popleft()

        if x == g:
            return a[x] 

        for i in range(2):
            nx = x + dx[i]
            
            if 1 <= nx <= f:
                if a[nx] == -1:
                    a[nx] = a[x] + 1
                    de.append(nx)
 
    return 'use the stairs'

print(bfs(g,s))

백준 알고리즘 5014번 : www.acmicpc.net/problem/5014

문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque

h,w=map(int,input().split())

a=[list(input()) for i in range(h)]

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

def bfs(s):
    ch=[[0]*w for i in range(h)] 
    de=deque()
    de.append(s)
    ch[s[0]][s[1]] = 1
    ma=0
    while len(de) != 0:
        m=de.popleft()
       
        for i in range(4):
            nx = m[0] + dx[i]
            ny = m[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w:
                if a[nx][ny] == 'L' and ch[nx][ny] == 0:
                    ch[nx][ny] = ch[m[0]][m[1]] + 1
                    de.append([nx,ny])
                    ma=max(ma, ch[nx][ny])
                    
    l.append(ma-1)

for i in range(h):
    for j in range(w):
        if a[i][j] == 'L':
            bfs([i,j])
            
print(max(l))

PyPy3로 제출했습니다.

백준 알고리즘 2589번 : www.acmicpc.net/problem/2589

문제

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

출력

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

플로이드 와샬 알고리즘

정답

from collections import deque

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]

b=[[] for i in range(n+1)]
r=[]

for i in range(m):
    x, y=a[i]
    b[x].append(y)
    b[y].append(x)

for i in range(1,len(b)): #중복 제거
    b[i]=list(set(b[i]))

def bfs(s):
    ch=[-1]*(n+1) # 값
    de=deque()
    de.append(s)
    ch[s]=0
        
    while de:
        x=de.popleft()
        
        for i in b[x]:            
            if ch[i] == -1:
                ch[i] = ch[x] + 1
                de.append(i)

    return sum(ch)-1
        
for i in range(1,n+1): #시작
    r.append(bfs(i))
    
r1=min(r)
print(r.index(r1) + 1)

모든 사람과 케빈 베이컨 게임을 하고 나오는 단계의 합을 구한 뒤 순서대로 리스트에 넣어주었습니다.

리스트에서 가장 작은 수를 찾아 해당 위치로 케빈 베이컨의 수가 가장 작은 사람을 출력했습니다.

백준 알고리즘 1389번 : www.acmicpc.net/problem/1389

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

예제 입력과 출력

알고리즘 분류

BFS
시뮬레이션 

정답

from collections import deque

r,c=map(int,input().split())

a=[list(input()) for i in range(r)]
ch=[[-1]*c for i in range(r)]
ch2=[[-1]*c for i in range(r)]

de=deque()
de2=deque()

for i in range(r):
    for j in range(c):
        if a[i][j] == 'D':
            d1, d2 = i, j
        if a[i][j] == 'S':
            s1, s2 = i, j
            de.append([s1, s2])
            ch[s1][s2]=0
        if a[i][j] == '*':
            w1, w2 = i, j
            de2.append([w1,w2])
            ch2[w1][w2]=0

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

def bfs2(): 
    
    while de2:
        x, y = de2.popleft()

        for i in range(4):
            nx = x +dx[i]
            ny = y +dy[i]

            if 0 <= nx < r and 0 <= ny < c:
                if a[nx][ny] == '.' and ch2[nx][ny] == -1:
                    ch2[nx][ny] = ch2[x][y] + 1
                    de2.append([nx,ny])

def bfs():
    
    while de:
        x, y=de.popleft()

        for i in range(4):
            nx = x +dx[i]
            ny = y +dy[i]

            if 0 <= nx < r and 0 <= ny < c:
                if ch[nx][ny] == -1 and (a[nx][ny] == '.' or a[nx][ny] == 'D'):
                    if ch[x][y] + 1 < ch2[nx][ny] or ch2[nx][ny] == -1 :
                        ch[nx][ny] = ch[x][y] + 1
                        de.append([nx,ny])

bfs2()
bfs()

if ch[d1][d2] == -1:
    print('KAKTUS')
else:
    print(ch[d1][d2])

물이 찰 예정인 시간을 BFS를 이용해 구하고 ch2 리스트에 저장합니다.

그 후 고슴도치의 이동을 BFS를 이용해 구합니다.

이 때 주의할 점은 고슴도치는 물이 차오르기 전이나 물이 차오르지 않은 곳을 이동할 수 있다는 점입니다.

백준 알고리즘 3055번 : www.acmicpc.net/problem/3055