그래프탐색의 기본이 되는 DFS, BFS 인데 사실 둘이 코드도 거의 유사하고, 문제들도 특정 문제들을 뺴면 둘다 사용해서 풀 수 있다. 보통은 BFS로 많이 푸는것같다.
그래프의 탐색이지만, 실제로는 격자위에서 움직이는 문제가 더 많다. 만약 그래프 탐색이라면 자료구조의 그래프를 참고하여 인접리스트, 연결리스트, 리스트의 리스트 등을 이용하여 그래프를 표현하면 된다.
격자에서 사용하는거라면 dx dy 테크닉과 결합해서 사용하면 된다.
아래부터는 주로 사용되는 격자 dfs bfs의 코드를 설명하겠다.
DFS
def inRange(x, y):
return 0 <= x < n and 0 <= y < n
def can_go(x, y):
if not inRange(x,y):
return False
if visited[x][y]:
return False
if grid[x][y] == 0: # 문제에 맞는 조건 쓰기
return False
return True
def push(x, y):
# 문제에 맞는 조건 쓰기
visited[x][y] = 1
dfs(x,Y)
def dfs(x, y):
dxs = [1,-1,0,0]
dys = [0,0,1,-1]
for dx, dy in zip(dxs, dys):
nx = dx + x
ny = dy + y
if can_go(nx, ny):
push(nx, ny)dfs는 재귀함수 형식으로 구현되는데, 방문 할떄마다 push 함수를 통해 조건들을 정리하고 visited를 1로 바꾼다음 다시 진행해서 dfs를 실행하는 방식이다.
can_go와 push를 잘 조정하고 visited 를 조건에 따라 초기화 하는것이 문제풀이의 핵심이다.
마을 구분하기
n*n격자안에서 벽으로 가로막혀 있고, 총 몇개의 구간이 생기는 지 물어보는 문제이다. 비슷한 유형으로 자주 출제되니 알아두면 좋다.
n = int(input())
visited = [[0 for _ in range(n)]for _ in range(n)] # for whole
temp_visited = [[0 for _ in range(n)]for _ in range(n)] # reset after every search
villager = []
cnt = 0
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
def inRange(x, y):
return 0 <= x < n and 0 <= y < n
def can_go(x, y):
if not inRange(x, y):
return False
if visited[x][y] or grid[x][y] == 0:
return False
return True
def push(x, y):
global cnt
visited[x][y] = 1
cnt += 1
dfs(x, y)
def dfs(x, y):
global cnt
dxs = [1, -1, 0, 0]
dys = [0, 0, -1, 1]
for dx, dy in zip(dxs, dys):
nx = x + dx
ny = y + dy
if can_go(nx, ny):
push(nx, ny)
for i in range(n):
for j in range(n):
if not visited[i][j] and grid[i][j] != 0:
cnt = 0
push(i, j)
villager.append(cnt)
print(len(villager))
vi = sorted(villager)
for i in vi:
print(i)뿌요뿌요
n*n 격자안에서 같은숫자간에서 dfs 탐색을하고 그 크기가 4이상이면 블럭으로 처리하는 프로그램이다.
n = int(input())
grid = []
cnt = 0
max_num = 0
block = 0
for _ in range(n):
grid.append(list(map(int, input().split())))
visited = [[0 for _ in range(n)] for _ in range(n)]
def inRnage(x, y):
return 0 <= x < n and 0 <= y < n
def can_go(nx, ny, x, y):
if not inRnage(nx, ny):
return False
if visited[nx][ny] or grid[x][y] != grid[nx][ny]:
return False
return True
def push(x, y):
global cnt
visited[x][y] = 1
cnt += 1
dfs(x, y)
def dfs(x, y):
global max_num, block, cnt
dxs = [-1,1,0,0]
dys = [0,0,1,-1]
for dx, dy in zip(dxs, dys):
nx = dx + x
ny = dy + y
if can_go(nx, ny, x, y):
push(nx, ny)
for i in range(n):
for j in range(n):
if not visited[i][j]:
push(i, j)
if cnt >= 4:
block += 1
max_num = max(max_num, cnt)
cnt = 0
print(block, max_num)사실 별로 어려울게 없는게, dfs를 1회 수행할때마다 cnt를 1씩 늘리고, cnt가 4 이상이면 block을 1씩 늘리는식으로 하면 된다. 어차피 다른 숫자들간에 탐색이기에 visited를 초기화 하거나 따로 손댈 필요가 없다
BFS
BFS 는 재귀가 아니라 queue를 사용하는 함수이다. 다만, 파이썬에서 풀때는 queue가 아니다 deque를 사용해야하는데, 피이썬queue는 동기화 작업이 들어가서 시간복잡도가 매우 불편하기 떄문이다.
bfs도 dfs랑 비슷한 구조를 가지고 있는데 bfs에서는 큐를 이용한다는점만이 다르다.
def inRange(x, y):
return 0 <= x < n and 0 <= y < m
def can_go(x, y):
if not inRange(x, y):
return False
if visited[x][y] or grid[x][y] == 0:
return False
return True
def push(x, y):
visited[x][y] = 1
q.append((x,y))
def bfs():
dxs = [1, -1, 0, 0]
dys = [0, 0, -1, 1]
while q:
x, y = q.popleft()
for dx, dy in zip(dxs, dys):
nx = x + dx
ny = y + dy
if can_go(nx, ny):
push(nx, ny)
push(0,0)
bfs()이런식으로 queue에 집어넣고, 하나씩 빼면서 측정하면 된다.
돌 잘 치우기
bfs에서는 랜덤한 지점에서 시작해서 어떤 경우 가장 최적의 결과가 나오는지 물어보는 문제가 많다. 이러한 경우 랜덤한 지점선택을 backtracking으로 선택하고 그 점들에 대해서 bfs를 실행하면서 한번 끝날때마다 기록하고 visited를 초기화해주는 작업이 필요하다.
from collections import deque
import copy
n, k, r = map(int, input().split())
q = deque()
cnt = 0
max_num = 0
grid = []
rock_info = []
remover = []
sp = []
visited = [[0 for _ in range(n)]for _ in range(n)] # for whole
for _ in range(n):
grid.append(list(map(int, input().split())))
temp_grid = copy.deepcopy(grid)
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
rock_info.append((i, j))
rock_cnt = len(rock_info)
for _ in range(k):
x, y = tuple(map(int, input().split()))
x -= 1
y -= 1
sp.append((x, y))
def inRange(x, y):
return 0 <= x < n and 0 <= y < n
def can_go(x, y):
if not inRange(x, y):
return False
if visited[x][y] or temp_grid[x][y] == 1:
return False
return True
def push(x, y):
global cnt
visited[x][y] = 1
cnt += 1
q.append((x,y))
def bfs():
dxs = [1, -1, 0, 0]
dys = [0, 0, -1, 1]
while q:
x, y = q.popleft()
for dx, dy in zip(dxs, dys):
nx = x + dx
ny = y + dy
if can_go(nx, ny):
push(nx, ny)
def change_grid():
global max_num, cnt, temp_grid
temp_grid = copy.deepcopy(grid)
for i in remover:
x, y = rock_info[i]
temp_grid[x][y] = 0
# after finishing changes
# do bfs to find the movement
for x, y in sp:
if visited[x][y] != 1:
push(x, y)
bfs()
max_num = max(max_num, cnt)
cnt = 0
def move_rock(curr_num, digit):
global visited
if curr_num == rock_cnt:
if digit == r:
#print(remover)
change_grid()
visited = [[0 for _ in range(n)] for _ in range(n)] # for whole
return
remover.append(curr_num)
move_rock(curr_num + 1, digit + 1)
remover.pop()
move_rock(curr_num + 1, digit)
move_rock(0, 0)
print(max_num)우리는 하나
기존의 1과 0으로만 구분되던 벽이 숫자 여러개로 나오고 특정 조건하에서만 움직일수있는 문제들도 나오는데 이러한 문제도 그런부류이다.
can_go를 잘 조절하면 된다.
from collections import deque
q = deque()
max_num = 0
cnt = 0
n, k, u, d = map(int, input().split())
grid = []
city = []
for _ in range(n):
grid.append(list(map(int, input().split())))
visited = [[0 for _ in range(n)] for _ in range(n)]
def inRange(x, y):
return 0 <= x < n and 0 <= y < n
def can_go(nx, ny, x, y):
if not inRange(nx, ny):
return False
if visited[nx][ny]:
return False
if not u <= abs(grid[x][y] - grid[nx][ny]) <= d:
return False
return True
def push(x, y):
global cnt
visited[x][y] = 1
cnt += 1
q.append((x,y))
bfs()
def do_math():
global max_num
for i in city:
x = i // n
y = i % n
if not visited[x][y]:
push(x, y)
max_num = max(max_num, cnt)
def bfs():
dxs = [1,-1,0,0]
dys = [0,0,1,-1]
while q:
x, y = q.popleft()
for dx, dy in zip(dxs, dys):
nx = x + dx
ny = y + dy
if can_go(nx, ny, x, y):
push(nx, ny)
def pick_city(curr_num, counter):
global cnt, visited
if counter == k:
do_math()
cnt = 0
visited = [[0 for _ in range(n)] for _ in range(n)]
return
if curr_num == n*n:
return
city.append(curr_num)
pick_city(curr_num + 1, counter + 1)
city.pop()
pick_city(curr_num +1, counter)
pick_city(0, 0)
print(max_num)BFS 최소경로
BFS로 최소한의 경로를 찾는 문제가 나오기도 한다. 꼭 격자의 형태로 나오는것이 아니라서, 격자가 아니라면 이동가능한 범위들을 체크하고 그것들을 그래프로 묶어주면 된다.
그리고 난 후, dx dy로 재구성하면 된다.
나이트
특정지점에서 특정저점까지 체스말 나이트가 갈수 있는지 없는지 간다면 몇번에 가는지 알아보는 문제이다.
from collections import deque
q = deque()
n = int(input())
sx, sy, ex, ey = map(int, input().split())
sx -= 1
sy -= 1
ex -= 1
ey -= 1
grid = [[0 for _ in range(n)]for _ in range(n)]
step = [[0 for _ in range(n)]for _ in range(n)]
visited = [[0 for _ in range(n)]for _ in range(n)]
def inRange(x, y):
return 0 <= x < n and 0 <= y < n
def can_go(x, y):
if not inRange(x, y):
return False
if visited[x][y]:
return False
return True
def push(x, y, s):
global cnt
visited[x][y] = 1
step[x][y] = s
q.append((x,y))
def bfs():
dxs = [-2,-2,-1,1,2,2,1,-1]
dys = [-1,1,2,2,1,-1,-2,-2]
while q:
x, y = q.popleft()
for dx, dy in zip(dxs, dys):
nx = x + dx
ny = y + dy
if can_go(nx, ny):
push(nx, ny, step[x][y] + 1)
push(sx, sy, 0)
bfs()
if visited[ex][ey] == 1:
print(step[ex][ey])
else:
print(-1)비를 피하기
사람이 벽을 피해 특정한 공간에 갈 수 있는지 파악하는 문제이다. 흔히들 사람을 기준으로 bfs를 돌릴것이다. 물론 사람 기준으로 bfs를 돌려도 답은 나오지만 시간이 꽤 오래걸리게 된다. 따라서 특정한 공간을 기준으로 사람까지의 거리가 얼마나 되는지 bfs를 하는것이 더 효율적이다
from collections import deque
q = deque()
n, h, m = map(int, input().split())
step = [[0 for _ in range(n)]for _ in range(n)]
visited = [[0 for _ in range(n)]for _ in range(n)]
grid = []
sp = []
shelter = []
for i in range(n):
temp = list(map(int, input().split()))
grid.append(temp)
for j in range(n):
if temp[j] == 3:
shelter.append((i, j))
if temp[j] == 2:
sp.append((i, j))
def inRange(x, y):
return 0 <= x < n and 0 <= y < n
def can_go(x, y):
if not inRange(x, y):
return False
if visited[x][y]:
return False
if grid[x][y] == 1:
return False
return True
def push(x, y, s):
visited[x][y] = 1
step[x][y] = s
q.append((x, y))
def bfs():
dxs = [1, -1, 0, 0]
dys = [0, 0, 1, -1]
while q:
x, y = q.popleft()
for dx, dy in zip(dxs, dys):
nx = x + dx
ny = y + dy
if can_go(nx, ny):
push(nx, ny, step[x][y] + 1)
for elem in shelter:
x, y = elem[0], elem[1]
push(x, y, 0)
bfs()
for i in range(n):
for j in range(n):
if grid[i][j] != 2:
print(0, end = ' ')
else:
if not visited[i][j]:
print(-1, end = ' ')
else:
print(step[i][j], end = ' ')
print()4가지 연산을 이용하여 1을 만들기
- 현재숫자에서 1 빼기
- 현재숫자에서 1 더하기
- 현재숫자에서 2로 나누어 떨어지면 2로 나누기
- 현재숫자에서 3으로 나누어 떨어지면 3으로 나누기
이러한 문제를 푼다고 할때 백트래킹으로도 풀수는 있지만 time limit에 걸리게된다.
이는 숫자 n으로부터 저 모든 결과를 수행한 결과들이 그래프의 노드가 되어 서로 연결된다고 생각한 후, 문제를 풀면 된다.
import sys
import enum
sys.setrecursionlimit(100000)
OPERATOR_NUM = 4
INT_MAX = sys.maxsize
class OPERATOR(enum.Enum):
SUBTRACT = 0
ADD = 1
DIV2 = 2
DIV3 = 3
n = int(input())
ans = INT_MAX
# num이라는 값에 해당 operator를 사용할 수 있는지를 판단합니다.
# 2로 나누거나 3으로 나누려는 경우 num이 해당 값으로 나누어 떨어질 때에만
# 해당 연산을 사용 가능합니다.
def possible(num, op):
if op == OPERATOR.SUBTRACT.value or op == OPERATOR.ADD.value:
return True
elif op == OPERATOR.DIV2.value:
return num % 2 == 0
else:
return num % 3 == 0
# num에 op 연산을 수행했을 때의 결과를 반환합니다.
def calculate(num, op):
if op == OPERATOR.SUBTRACT.value:
return num - 1
elif op == OPERATOR.ADD.value:
return num + 1
elif op == OPERATOR.DIV2.value:
return num // 2
else:
return num // 3
# 모든 가지수를 다 조사해보며 최소 연산 횟수를 계산합니다.
def find_min(num, cnt):
global ans
# 1이 되었을 경우 답이랑 비교하여 갱신합니다.
if num == 1:
ans = min(ans, cnt)
return
# 답은 최대 n - 1을 넘을수는 없으므로
# 더 이상 탐색을 진행하지 않습니다.
if cnt >= n - 1:
return
# 4가지의 연산을 시도해 봅니다.
# 해당 연산을 쓸 수 있는 경우에만
# 더 탐색을 진행합니다.
for i in range(OPERATOR_NUM):
if possible(num, i):
find_min(calculate(num, i), cnt + 1)
# 모든 가지수를 다 조사해보며 최소 연산 횟수를 계산합니다.
find_min(n, 0)
print(ans)상한 귤
복잡해보이는 문제이지만, 각 지점으로부터 bfs를 실행하고 가장 작은 값을 기록해주는 문제이다
from collections import deque
q = deque()
n, k = tuple(map(int, input().split()))
sp = []
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
visited = [[0 for _ in range(n)] for _ in range(n)]
step = [[0 for _ in range(n)]for _ in range(n)]
temp = [[0 for _ in range(n)]for _ in range(n)]
def inRange(x, y):
return 0 <= x < n and 0 <= y < n
def push(x, y, s):
visited[x][y] = 1
temp[x][y] = s
q.append((x, y))
def can_go(x, y):
if not inRange(x, y):
return False
if visited[x][y]:
return False
if grid[x][y] != 1:
return False
return True
def bfs():
dxs = [1, -1, 0, 0]
dys = [0, 0, 1, -1]
while q:
x, y = q.popleft()
for dx, dy in zip(dxs, dys):
nx = x + dx
ny = y + dy
if can_go(nx, ny):
push(nx, ny, temp[x][y] + 1)
def overWrite():
for i in range(n):
for j in range(n):
if step[i][j] == 0:
step[i][j] = temp[i][j]
elif step[i][j] > temp[i][j] and temp[i][j] != 0:
step[i][j] = temp[i][j]
for i in range(n):
for j in range(n):
if grid[i][j] == 2:
sp.append((i, j))
push(i, j, 0) # temp is created
bfs()
overWrite()
temp = [[0 for _ in range(n)] for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if grid[i][j] == 0: # empty from the first time
step[i][j] = -1 # mark as -1
for i in range(n):
for j in range(n):
if step[i][j] == 0:
step[i][j] = -2
for i in sp:
x = i[0]
y = i[1]
step[x][y] = 0
for i in range(n):
for j in range(n):
print(step[i][j], end = ' ')
print()
# 4 1
# 0 0 0 0
# 0 0 1 0
# 1 1 1 0
# 0 2 1 1다만 주의해야할 것은 최초로 기록할때는 모든것을 기록해줘야 한다는점과, 한번 bfs 하고 나면 초기하를 해야한다는것이다.
마무리
dfs bfs는 백트래킹이랑 비슷하게 풀려서 혼동할 수 있다.
문제를 많이 풀어봐야 알 수 있는 부분인듯하다.
