IT-garden

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

정답

from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())

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

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

def bfs(s1,s2):
    de=deque()
    de.append([s1,s2])
    ch[s1][s2]=1

    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:
                    ch[nx][ny] = 1
                    de.append([nx,ny])

for i in range(101): #물에 잠기는 지점 설정
    ch=[[0]*n for i in range(n)]
    c=0

    for j in range(n):
        for k in range(n):
            if a[j][k] <= i:
                ch[j][k] = 1
 
    for j in range(n):
        for k in range(n):
            if ch[j][k] == 0:
                bfs(j,k)
                c += 1

    l.append(c)

print(max(l))    

높이에 대한 경우의 수를 모두 생각했습니다.

높이보다 낮은 수의 위치들을 1로 해서 BFS를 해주고 안전 영역을 계산했습니다.

그 후 가장 큰 안전 영역의 값을 출력했습니다.

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

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

정답

from collections import deque

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

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

l=[]

for i in range(k):
    x1, y1, x2, y2=map(int,input().split())

    for j in range(x1,x2):
        for k in range(y1,y2):
            a[k][j]=1
            
def bfs(s1,s2):
    de=deque()
    de.append([s1,s2])
    a[s1][s2]=1
    c=1

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

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

            if 0 <= nx < m and 0 <= ny < n:
                if a[nx][ny] == 0:
                    
                    a[nx][ny] = 1
                    c += 1
                    de.append([nx,ny])
    l.append(c)

for i in range(m):
    for j in range(n):
        if a[i][j] == 0:
            bfs(i,j)

print(len(l))
l.sort()
for i in l:
    print(i,end=' ')

전체 모눈종이에서 시작점 x1부터 끝점 x2까지, 시작점 y1부터 끝점 y2까지를 1로 채워주고 BFS를 이용해 영역을 구해주었습니다.

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque

n,k=map(int,input().split())

def bfs(n,k):
    de=deque()
    de.append(n)
    a=[0]*100001

    while de:
        x=de.popleft()
        
        if x == k:
            return a[x]
            
        for i in (x-1,x+1,x*2):
            if 0 <= i < 100001 and a[i] == 0:
                a[i] = a[x]+1
                de.append(i)

print(bfs(n,k))

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

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 몇 번만에 이동할 수 있는지 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque

n=int(input())
dx=[-2, -1, 1, 2, 2, 1, -1, -2]
dy=[1, 2, 2, 1, -1, -2, -2, -1]

def bfs(s,e):
    de=deque()
    de.append(s)
    ch[s[0]][s[1]] = 1
    
    while de:
        x, y=de.popleft()

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

            if 0 <= nx < l and 0 <= ny < l:
                if ch[nx][ny] == 0:
                    a[nx][ny] = a[x][y] + 1
                    ch[nx][ny] = 1
                    de.append([nx,ny])

                    if nx == e[0] and ny == e[1]:
                        return a[nx][ny]
    
for i in range(n):
    l = int(input())
    s = list(map(int, input().split()))
    e = list(map(int, input().split()))
    
    a=[[0]*l for j in range(l)] #이동 횟수 리스트
    ch=[[0]*l for j in range(l)] #방문 여부
    
    if s == e:
        c = 0
    else:
        c = bfs(s,e)
        
    print(c)

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

문제

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque

n=int(input())
n1,n2=map(int,input().split())
m=int(input())
a=[[]*(n+1) for i in range(n+1)]
ch=[0]*(n+1)

for i in range(m):
    m1,m2=map(int,input().split())
    a[m1].append(m2)
    a[m2].append(m1)

def bfs(s):
    de=deque()
    de.append(s)
    ch[s]=0

    while de:
        x=de.popleft()

        for i in a[x]:
            if ch[i] == 0:
                ch[i] = ch[x]+1
                de.append(i)

bfs(n1)

if ch[n2] == 0:
    print(-1)
else:
    print(ch[n2])

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

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

정답

from collections import deque

n,m=map(int,input().split())
a=[[]*(n+1) for i in range(n+1)]
ch=[0]*(n+1)

for i in range(m):
    u,v= map(int,input().split())
    a[u].append(v)
    a[v].append(u)

def bfs(s):
    de=deque()
    de.append(s)
    ch[s]=1
    
    while de:
        x=de.popleft()

        for i in a[x]:
            if ch[i] == 0:
                ch[i] = 1
                de.append(i)

c=0

for i in range(1,n+1):
    if ch[i] == 0:
        c += 1
        bfs(i)

print(c)    

파이썬 시간초과로 PyPy3로 제출했습니다.

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