DFS(깊이 우선 탐색)
- 깊은 부분을 우선적으로 탐색 -> 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 도랑가 다른 경로로 탐색하는 알고리즘
- 스택 자료구조에 기초 (재귀 함수로 간결하게 구현 가능)
BFS(너비 우선 탐색)
- 가까운 부분을 우선적으로 탐색
- 큐 자료구조에 기초
- 일반적으로 수행시간이 DFS 보다 좋음
#18352 특정 거리의 도시 찾기
🔗https://www.acmicpc.net/problem/18352
문제
어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.
이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.
입력
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.
출력
X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.
이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.
생각
- bfs로 시작 노드부터 모든 노드까지의 탐색 진행 후 그 거리를 저장한다.
- 거리가 저장된 리스트중 K인 노드를 찾아 출력
코드
import sys
from collections import deque
def bfs(graph, start, answer):
queue=deque([start])
while queue:
v=queue.popleft()
for w in graph[v]:
if answer[w]==-1: #방문하지 않은 노드면 추가 및 거리 갱신
answer[w]=answer[v]+1
queue.append(w)
city, road, distance, start = map(int,sys.stdin.readline().split())
answer= [-1]*(city+1) #방문 여부 및 거리 저장
answer[start]=0
#인접리스트
graph=[ [] for _ in range(city+1) ]
for _ in range(road):
a,b = map(int,sys.stdin.readline().split())
graph[a].append(b)
bfs(graph, start, answer)
if answer.count(distance):
for i in range(1,city+1):
if answer[i]==distance:
print(i)
else:
print("-1")#14502 연구소
🔗https://www.acmicpc.net/problem/14502
문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
생각
어케 불과 20일전에 푼 문제임에도 불구하고
푸는데 어려움을 겪을 수 있는가......
- 세울 수 있는 모든 경우의 벽 세우기
- bfs로 바이러스 퍼뜨리기 (최대 영역 크기 갱신해주기)
- 최대 영역 크기 출력
늘 1번에서 어려움을 겪는 것 같다.
코드
#연구소
from collections import deque
import sys
import copy
dx=[-1,1,0,0]
dy=[0,0,-1,1]
#바이러스 퍼뜨리기 및 최대 영역 크기 갱신
def bfs():
global max_result
queue=deque()
tmp=copy.deepcopy(graph)
for i in range(n):
for j in range(m):
if graph[i][j]==2:
queue.append((i,j))
while queue:
y,x=queue.popleft()
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if nx>=0 and ny>=0 and ny<n and nx<m:
if tmp[ny][nx]==0:
tmp[ny][nx]=2
queue.append((ny,nx))
result=0
for i in range(n):
for j in range(m):
if tmp[i][j]==0:
result+=1
max_result=max(result,max_result)
#벽 세우기
def build(cnt):
if cnt==3:
bfs()
return
for i in range(n):
for j in range(m):
if graph[i][j]==0:
graph[i][j]=1
build(cnt+1)
graph[i][j]=0
#이게 포인트인듯.. 벽을 세울 수 있는 모든 경우를 체크 해줘야하기 때문에
#재귀 뒤에 graph[i][j]=0을 꼭 넣어줘야함
n,m=map(int,sys.stdin.readline().split())
graph=[]
for i in range(n):
graph.append(list(map(int,sys.stdin.readline().split())))
max_result=0
build(0)
print(max_result)#18405 경쟁적 전염
🔗https://www.acmicpc.net/problem/18405
문제
NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.
시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.
예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.
1초가 지난 후에 시험관의 상태는 다음과 같다.
2초가 지난 후에 시험관의 상태는 다음과 같다.
결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.
입력
첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)
출력
S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.
생각
고려해야 하는 것
- 바이러스의 종류 (클 수록 우선이어야 함)
- 시간 (s초가 되면 멈추도록)
그러므로 큐에 (바이러스 종류, 시간, y좌표, x좌표) 를 넣어, 바이러스 종류 기준으로 오름차순 정렬을 해줘야한다!
코드
from collections import deque
import sys
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def bfs():
que=[]
for i in range(n):
for j in range(n):
if graph[i][j]>0:
que.append((graph[i][j],0,i,j)) #바이러스 종류, 초, y좌표, x좌표
que.sort()
queue=deque(que) #point: 정렬을 해준 후 deque로 변환 (deque는 내장된 sort함수가 없다.)
while queue:
virus,sec,y,x=queue.popleft()
if sec==s: #s초가 되면 멈추자.
return
for i in range(4):
ny=y+dy[i]
nx=x+dx[i]
if ny>=0 and nx>=0 and ny<n and nx<n:
if graph[ny][nx]==0:
graph[ny][nx]=virus
queue.append((graph[ny][nx],sec+1,ny,nx))
n,virus=map(int,sys.stdin.readline().split())
graph=[]
for _ in range(n):
graph.append(list(map(int,sys.stdin.readline().split())))
s,a,b=map(int,sys.stdin.readline().split())
bfs()
print(graph[a-1][b-1])#14888 연산자 끼워넣기
🔗https://www.acmicpc.net/problem/14888
문제
N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.
- 1+2+3-4×5÷6
- 1÷2+3+4-5×6
- 1+2÷3×4-5+6
- 1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
- 1+2+3-4×5÷6 = 1
- 1÷2+3+4-5×6 = 12
- 1+2÷3×4-5+6 = 5
- 1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
출력
첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
생각
처음에는 이게 왜 dfs/bfs지? 라는 생각이 들었던 것 같다.
그러고 다시 확인하니까, 수의 순서를 바꿀 수 없다라는 조건이 눈에 띄었고, 아 그러면 모든 경우를 bfs/dfs를 이용해서 전체 탐색하는 방향으로 풀어야겠구나! 라는 생각을 했다.
코드
import sys
n=int(sys.stdin.readline().rstrip())
number=list(map(int,sys.stdin.readline().split()))
plus,minus,multi,divide=map(int,sys.stdin.readline().split())
min_value=1000000001
max_value=-1000000001
def dfs(v,value):
global plus,minus,multi,divide,min_value,max_value
if v==n:
min_value=min(min_value,value)
max_value=max(max_value,value)
return
if plus>0:
plus-=1
dfs(v+1,value+number[v])
plus+=1
if minus>0:
minus-=1
dfs(v+1,value-number[v])
minus+=1
if multi>0:
multi-=1
dfs(v+1,value*number[v])
multi+=1
if divide>0:
divide-=1
dfs(v+1,int(value/number[v]))
divide+=1
dfs(1,number[0])
print(max_value,min_value,sep="\n")