알고리즘 스터디 - DFS/BFS 3문제 풀이(feat. 섬의 개수, 물통, 다리 만들기2)

백준 4963번 : 섬의 개수 - 실버 2

이 문제는 x, y 좌표를 이용해 연결되어 있는 섬을 판별하기 위하여 BFS 알고리즘을 유도하는 문제이다. 주의할 점은 보통 상하좌우 4 방향으로 움직이지만 여기서는 대각선도 이동할 수 있어 8 방향으로 움직인다는 것이다.

알고리즘 코드

import sys

def bfs(x, y, w, h, land):
    dx = [0, 0, -1, 1, 1, -1, 1, -1]
    dy = [-1, 1, 0, 0, -1, -1, 1, 1]

    q = [(x, y)]

    while q:
        current_x, current_y = q.pop(0)

        for i in range(8):
            new_x, new_y = current_x+dx[i], current_y+dy[i]

            if 0 <= new_x < w and 0 <= new_y < h:
                if land[new_y][new_x] == 1:
                    land[new_y][new_x] = 0
                    q.append((new_x, new_y))
    
    return 1

while True:
    w, h = map(int, sys.stdin.readline().split())

    if w == 0 and h == 0:
        break

    land = []
    for _ in range(h):
        land.append(list(map(int, sys.stdin.readline().split())))
    
    answer = 0
    for i in range(h):
        for j in range(w):
            if land[i][j] == 1:
                answer += bfs(j, i, w, h, land)
    
    print(answer)

백준 2251번 : 물통 - 골드 5

물통 같은 경우 BFS/DFS가 visited로 중복 계산을 피하는 것처럼 수많은 경우의 수를 구하고 물통 A가 비어있을 때 C의 용량을 구하는 것이다. 살짝 경우의 수를 작성하는 것이 시간이 걸릴 수 있지만 그래도 실행 시간은 매우 짧다.

알고리즘 코드

import sys

a, b, c = map(int, sys.stdin.readline().split())

result = []
status = []
q = [(0, 0, c)]

while q:
    first, second, third = q.pop(0)ㅁ

    if first == 0 and third not in result:
        result.append(third)

    if (first, second, third) not in status:
        status.append((first, second, third))
        # a exists
        if first != 0:
            # a->b
            if (b-second) <= first:
                q.append((first - (b-second), b, third))
            else:
                q.append((0, second+first, third))
            
            # a->c
            if (c-third) <= first:
                q.append((first-(c-third), second, c))
            else:
                q.append((0, second, third+first))
        
        # b exists
        if second != 0:
            # b->a
            if (a-first) <= second:
                q.append((a, second-(a-first), third))
            else:
                q.append((first+second, 0, third))
            
            # b->c
            if (c-third) <= second:
                q.append((first, second-(c-third), c))
            else:
                q.append((first, 0, third+second))
        
        # c exists
        if third != 0:
            # c->a
            if (a-first) <= third:
                q.append((a, second, third-(a-first)))
            else:
                q.append((first+third, second, 0))
            
            # c->b
            if (b-second) <= third:
                q.append((first, b, third-(b-second)))
            else:
                q.append((first, second + third, 0))

print(*sorted(result))

백준 17472번 : 다리 만들기 2

이 문제 같은 경우는 솔직히 너무 어려웠다. 진작에 질문 검색에서 다른 반례들을 찾아보며 해결했어야 했는데 안보고 하다가 나중에 다른 사람들이 올려준 테스트 케이스를 기반으로 수정에 수정을 거듭해 10번 시도하고 드디어 성공 했다. 알고리즘 구성은 BFS -> Brute Force -> Kruskal 이 3가지로 알고리즘을 순서대로 잘 쓰면 되지만 문제는 어떤 경우에 실패하는지 생각하지 못하기 때문에 어렵다. 알고리즘이 사고력을 요하는 문제임을 다시 깨닫게 된 문제였다. 열심히 머리를 굴리자

알고리즘 코드

import sys

# n, m input
n, m = map(int, sys.stdin.readline().split())

# sea, land
land = []
visited = [[False] * m for _ in range(n)]

for _ in range(n):
    land.append(list(map(int, sys.stdin.readline().split())))

# position of island
island = []

# Using BFS, find an individual algorithm
def bfs(x, y):
    q = [(x, y)]
    coordinate = set()
    coordinate.add((x, y))

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    while q:
        current_x, current_y = q.pop(0)

        for i in range(4):
            new_x = current_x + dx[i]
            new_y = current_y + dy[i]

            if 0 <= new_x < m and 0 <= new_y < n and land[new_y][new_x] == 1 and visited[new_y][new_x] == False:
                visited[new_y][new_x] = True
                coordinate.add((new_x, new_y))
                q.append((new_x, new_y))
    return coordinate

for i in range(n):
    for j in range(m):
        if land[i][j] == 1 and visited[i][j] == False:    
            island.append(bfs(j, i))


# Using Brute force, find the distance of two islands
edges = []

for i in range(len(island)):
    for j in range(len(island)):
        if i != j:
            min_distance = 101
            
            for x, y in island[i]:
                for next_x, next_y in island[j]:
                    if x == next_x:
                        if abs(y - next_y) > 2:
                            flag = False
                            bigger = max(y, next_y)
                            smaller = min(y, next_y)

                            for k in range(smaller+1, bigger):
                                if land[k][x] == 1:
                                    flag = True
                                    break
                            
                            if flag == False:
                                min_distance = min(min_distance, abs(y - next_y)-1)
                    
                    if y == next_y:
                        if abs(x - next_x) > 2:
                            flag = False
                            bigger = max(x, next_x)
                            smaller = min(x, next_x)

                            for k in range(smaller+1, bigger):
                                if land[y][k] == 1:
                                    flag = True
                                    break
                            
                            if flag == False:
                                min_distance = min(min_distance, abs(x - next_x)-1)
            
            if min_distance != 101 and (min_distance, j, i) not in edges:
                edges.append((min_distance, i, j)) 

edges.sort()
# Using mst Algorithm, find the minimum spanning tree
parent = [i for i in range(len(island))]

answer = 0

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x <= y:
        parent[y] = x
    else:
        parent[x] = y

edges.sort()

for edge in edges:
    weight, x, y = edge
    if find(x) != find(y):
        union(x, y)
        answer += weight

wrong = False
for i in range(len(island)):
    for j in range(len(island)):
        if find(i) != find(j):
            wrong = True
            break
    if wrong:
        break

if edges and wrong == False:
    print(answer)
else:
    print(-1)