[알고리즘] DFS/BFS - 백준 2644 4963 2667 7562 16234

DFS/BFS

깊이 우선 탐색 / 넓이 우선 탐색

설명은 이전 글에 있으니 생략하겠다.

 

 

 

백준 2644 촌수계산

from collections import deque

n = int(input())

p1, p2 = map(int, input().split())

m = int(input())
relat = []
res = []
visited = [False] * (n+1)

for _ in range(m):
    x, y = map(int, input().split())
    relat.append([x, y])
    relat.append([y, x])
    
graph = [[]]
for i in range(1, n+1):
    temp = []
    for x in relat:
        if x[0] == i:
            temp.append(x[1])
    graph.append(temp)
    
def dfs(start, ans):
    ans += 1
    visited[start] = True
    
    if start == p2:
        res.append(ans)
    
    for i in graph[start]:
        if not visited[i]:
            dfs(i, ans)
            
dfs(p1, 0)

if len(res) == 0:
    print(-1)
else:
    print(res[0] - 1)

 

백준 4963 섬의 개수

from collections import deque
ans = 0
def bfs(graph, x, y):
    global ans
    if not graph[x][y] or visited[x][y]:
        return
    visited[x][y] = 1
    q = deque()
    q.append((x, y))
    ans += 1
    while q:
        x, y = q.popleft()
        dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, 1), (-1, -1), (1, -1), (1, 1)]
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            
            if -1 < nx < h and -1 < ny < w and graph[nx][ny] and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))
res = []   
while True:
    ans = 0
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    
    visited = [[0 for _ in range(w)] for _ in range(h)]
    island = [list(map(int, input().split())) for _ in range(h)]

    
    for i in range(h):
        for j in range(w):
            bfs(island, i, j)
                
    res.append(ans)
    
for x in res:
    print(x)

 

백준 2667 단지번호붙이기

from collections import deque

n = int(input())

house = []

for _ in range(n):
    tmp = list(input())
    for i in range(len(tmp)):
        tmp[i] = int(tmp[i])
    house.append(tmp) 
    
def bfs(a, b):
    global cnt
    global anstmp
    global lis
    if not house[a][b] or visited[a][b]: return
    dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    q = deque([(a, b)])
    cnt += 1
    num = 0
    while q:
        x, y = q.popleft()
        num += 1
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            
            if nx in range(n) and ny in range(n) and not visited[nx][ny] and house[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))
    if num > 1:
        lis.append(num-1)
    else:
        lis.append(num)                
visited = [[False] * n for _ in range(n)]        
cnt = 0
lis = []
for i in range(n):
    for j in range(n):
        bfs(i, j)
        
print(cnt)
lis.sort()

for x in lis:
    print(x)

 

백준 7562 나이트의 이동

from collections import deque
T = int(input())

dxdy = [(-2, 1), (-1, 2), (-2, -1), (-1, -2), (2, 1), (1, 2), (2, -1), (1, -2)]

def bfs(graph, xx, yy):
    global cnt
    q = deque()
    q.append((xx,yy,cnt))
    while q:
        x, y, cnt = q.popleft()
        if x == want_x and y == want_y:
            return cnt
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            
            if nx in range(length) and ny in range(length) and not visited[nx][ny]:
                visited[nx][ny] += 1
                q.append((nx, ny, cnt +1))
                
for _ in range(T):
    length = int(input())
    cnt = 0
    pre_x, pre_y = map(int, input().split())
    want_x, want_y = map(int, input().split())
    chess = [[0] * length for _ in range(length)]
    visited = [[0] * length for _ in range(length)]
    print(bfs(chess, pre_x, pre_y))

큐를 꼭 (x,y)로만 할 필요는 없다는 점...

 

백준 16234 인구 이동

 

왜 마지막 풀때쯤 되면 머리가 안돌아갈까.. 구글링 해서 풀었다...

from collections import deque
N, L, R = map(int, input().split())
dxdy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

population = []

for _ in range(N):
    population.append(list(map(int, input().split())))
    
def bfs(i, j):
    q = deque()
    q.append((i, j))
    visited[i][j] = 1
    hap = [(i, j)]
    hapcnt = population[i][j]
    
    while q:
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            
            if nx in range(N) and ny in range(N) and not visited[nx][ny] and L <= abs(population[nx][ny] - population[x][y]) <= R:
                hap.append((nx, ny))
                visited[nx][ny] = 1
                q.append((nx, ny))
                hapcnt += population[nx][ny]
                
    for a, b in hap:
        population[a][b] = int(hapcnt / len(hap))
        
    return len(hap)

day = 0

while True:
    visited = [[0]*N for _ in range(N)]
    flag = False
    
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                if bfs(i, j) > 1:
                    flag = True
    if not flag:
        break
    
    day += 1
    
print(day)