1. 알고리즘 관련 공부
이번 주는 공부했던 알고리즘 지식을 정리하려 한다.
예제) 단지 번호 붙이기(DFS)
그림1과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸 다.철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한 다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.
대각선상에 집이 있는 경우는 연결된 것이 아니다.
그림2는 그림1을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지 에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
▣ 입력설명
첫 번째줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력 되고 그 다음 N줄에는 각각 N개의 자료(0 혹은 1)가 입력된다
▣ 출력설명
첫 번째줄에는 총 단지수를 출력하시오. 그리고 각 단지내의 집의 수를 오름차순으로 정렬하 여 한줄에 하나씩 출력하시오
▣ 입력예제 1
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
▣ 출력예제 1
3
7
8
9
해설)
이 문제는 DFS로 풀 수 있다. 각 단지를 정하기 위해 먼저 이중 for문으로 값이 1인 좌표를 찾고 값을 0으로 DFS를 돌린다. DFS가 돌 때마다 cnt에 +1을 한다. 그렇게 나온 cnt를 DFS가 끝난 후 리스트에 append한다. 그럼 이중 for문에서 다음 1을 찾는다. 이렇게 for문이 다 끝나면 리스트 내에 각 단지들의 집 갯수가 들어있다. 총 단지의 갯수는 len() 함수를 통해 도출한다.
dx = [-1,0,1,0]
dy = [0,1,0,-1]
# 단지, 집의 갯수 세기
# 이건 DFS나 BFS로 풀 수 있다.
# DFS를 통해 풀 떄는 백트래킹을 써서 구할 수 있다.
# 백트래킹으로 계속 뒤로 간 뒤에
# res라는 리스트를 생성하여 각 단지의 집 갯수를 append한다.
# 총 단지의 갯수는 len(res)를 하면 나온다.
def DFS(x,y):
global cnt
cnt+=1
# 방문 했으니 0으로 만든다.
board[x][y] = 0
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
DFS(xx,yy)
if __name__ == "__main__":
n = int(input())
# 입력 값에 띄어쓰기가 없으면 split()을 쓰지 않는다.
board = [list(map(int, input())) for _ in range(n)]
res = []
# board 탐색, 이중 for문을 돌아야한다.
for i in range(n):
for j in range(n):
# 1을 발견했을 때 이 때부터 퍼져나가야한다.
# 단지를 발견했다는 뜻이다.
# 집을 발견했다는 얘기
if board[i][j] == 1:
# 단지를 찾을 때마다 cnt를 초기화해야 한다.
cnt = 0
DFS(i,j)
# 단지의 집 갯수가 카운트가 다 되었을 때
# cnt를 res에 넣어준다.
res.append(cnt)
print(len(res))
# 오름차순 정렬
res.sort()
for x in res:
print(x)
예제) 섬나라 아일랜드(BFS 활용)
섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대 각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
만약 위와 같다면
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.
▣ 출력설명
첫 번째 줄에 섬의 개수를 출력한다.
▣ 입력예제 1
7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0
▣ 출력예제 1
5
해설)
이 문제는 위 문제랑 거의 똑같다. 다만 이번에는 BFS를 사용한다. 조건에 상하좌우와 대각선이라는 조건이 붙어있으므로
from collections import deque
# 12시 방향을 기준으로 시계방향
dx = [-1,-1,0,1,1,1,0,-1]
dy = [0,1,1,1,0,-1,-1,-1]
# 이 문제는 BFS로 8방향, 즉 대각선도 탐색한다.
# 섬이 몇 개 있는가, 동떨어진 지역을 세는 문제는 BFS의 경우 8방향을 탐색한다.
# 갯수만 세면된다. 전 문제 단지 번호붙이기 생각을 하자
n = int(input())
board = [list(map(int,input().split())) for _ in range(n)]
# 섬의 갯수
cnt = 0
# 큐
Q = deque()
# 섬이나 기타 영역 갯수를 세는 문제는 값이 1인 좌표를 찾는 것부터 시작한다.
# 단지 번호 붙이기를 생각하자
for i in range(n):
for j in range(n):
# 값이 1인 곳을 방문
if board[i][j] == 1:
# 방문한 곳을 체크
board[i][j] = 0
# 방문한 곳의 좌표를 큐에 넣는다.
# 튜플로 넣는다.
Q.append((i,j))
while Q:
temp = Q.popleft()
# 8방향
for k in range(8):
xx = temp[0] + dx[k]
yy = temp[1] + dy[k]
if 0<= xx < n and 0<= yy < n and board[xx][yy] == 1:
board[xx][yy] = 0
Q.append((xx,yy))
# 영역의 갯수를 세는 문제는 DFS 혹은 BFS가 한 번 끝났을 때 카운팅한다.
cnt+=1
print(cnt)
예제) 토마토(BFS 활용)
현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림 과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향 에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토 가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나 면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들 의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로 그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
▣ 입력설명
첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어진다. M은 상자의 가로 칸의 수, N 은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M, N ≤ 1,000 이다.
둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄 에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토 의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
▣ 출력설명
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
▣ 입력예제 1
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1
▣ 출력예제 1
4
해설)
정리가 가능하기에는 너무 양이 많다. 주석을 참고하기 바란다.
from collections import deque
# 토마토 창고에 있는 정보
# board라는 2차원 리스트에 지도 정보 저장
# dis라는 같은 크기의 빈 2차원 리스트
# 여기에 몇 일 만에 모든 박스가 썩는지 저장할 것임
# 원리는 결국 일반 dis와 같다.
# 방문하면 board의 값을 1로 바꾸어 저장한다.
# dis 리스트에 들어가는 값을 날짜라고 생각해도 된다.
# board를 2차원 탐색을 한다.
# 익은 토마토의 값을 큐에 넣는다.
# 큐에 익은 토마토의 위치를 다 넣는다.
# dx, dy 즉 4방향을 생각하자.
# 익은 토마토의 위치 튜플들을 큐에 넣어서 탐색한다.
# dis는 처음 위치는 0, 그 다음에 큐에서 나온 좌표들을 통해
# board에서 만약 x는 0..4, y는 0..6이고 방문 안 했고 board의 값이 -1아니면
# 방문!! 즉 보드[x][y]의 값을 1로
# 상태 트리로 뻗는다
# 첫 부모는 0일에서 이미 익은 것들
# 다음 상태 트리 레벨은 1일 째에 익은 것들
# 그 다음 상태 트리 레벨은 2일 째에 익은 것들
# 이렇게 4방향 탐색으로 다음 레벨 노드들을 큐에 넣으면서 돌린다.
# 그 와중에 dis에 같은 좌표들의 값을 전 노드의 dis위치 값 +1을 한다.
dx = [-1, 0 ,1, 0]
dy = [0,1,0,-1]
n,m = map(int, input().split())
board = [list(map(int,input().split())) for _ in range(m)]
dis = [[0]*n for _ in range(m)]
Q = deque()
# 이중 for문을 돌면서 이미 익은 토마토를 찾는다.
# 행을 먼저 둬야한다. 조심!
for i in range(m):
for j in range(n):
if board[i][j] == 1:
Q.append((i,j))
# BFS 코드
# 찾고 바깥에서 뒤져야한다.
# 좌표만 찾을 거였다.
while Q:
temp = Q.popleft()
for i in range(4):
x = temp[0] + dx[i]
y = temp[1] + dy[i]
# bfs나 dfs나 경계선을 지키자
if 0<=x<m and 0<=y<n and board[x][y] == 0:
# 방문
board[x][y] = 1
dis[x][y] = dis[temp[0]][temp[1]] + 1
Q.append((x,y))
# 탐색 끝
# 모든게 익었는지 확인해야한다.
flag = 1
for i in range(m):
for j in range(n):
# 안 익은 토마토가 있으면
if board[i][j] == 0:
flag = 0
result = 0
if flag == 1:
# 최소 일 수 찾기
for i in range(m):
for j in range(n):
if dis[i][j] >result:
result = dis[i][j]
print(result)
else:
print(-1)
