1/1 WIL
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)