그래프 탐색

🧑‍💻 그래프 탐색

멀티잇 코딩테스트 러닝클래스'Python 5월반

 

 

구름이의 여행

연결되어 있는 섬들을 K개 이하로 갈 수 있는지 확인하는 것

• BFS를 이용하여, 최단 거리 구하기를 하였다

1번부터 N번 섬까지 못 갈 수도 있음

• 그러기 위해 flag를 이용하여, 못 가면 False 즉 NO 를 출력하도록 유도

 

N번 섬에 도착하면

• answer에다가 몇 번을 움직였는지 저장을 한 후, K번 이하인지 구별하기

from collections import deque

N, M, K = map(int, input().split())

island = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
queue = deque([])
answer, flag = 0, False

for _ in range(M):
    A, B = map(int, input().split())
    island[A].append(B)
    island[B].append(A)


visited[1] = True
queue.append((1, 0))

while queue:
    current = queue.popleft()

    for cur in island[current[0]]:
        if visited[cur] == False:
            visited[cur] = True
            queue.append((cur, current[1] + 1))

            if cur == N:
                answer, flag = current[1] + 1, True
                break

if answer <= K and flag == True:
    print('YES')
else:
    print("NO")

---

 

 

뭉친 K

K라는 값이 주어지만, K 기준으로 상하좌우에 같은 값이 있으면 뭉쳤다고 한다

• 제일 큰 뭉친 그룹의 크기를 출력한다

여기서 주어지는 좌표 기준으로 K 값을 알게 된다고 해서, 그 좌표를 기준으로 뭉친 그룹의 크기를 출력하는 것이 아니다

• 즉, 다른 뭉친 그룹 중, K 값일 때도 생각해야 한다

 

그래서 행렬을 한번은 완전탐색을 해야 한다

N = int(input())
r, c = map(int, input().split())
r, c = r - 1, c - 1

matrix = [list(map(int, input().split())) for _ in range(N)]

value = matrix[r][c]
dr, dc = [-1, 0, 0, 1], [0, -1, 1, 0]
answer = 0

for i in range(N):
    for j in range(N):

        temp = 0
        stack = []

        if matrix[i][j] == value and matrix[i][j] != "visited":
            matrix[i][j] = "visited"
            stack.append((i, j))
            temp += 1

            while stack:
                row, column = stack.pop()

                for k in range(4):
                    sr, sc = dr[k] + row, dc[k] + column

                    if 0 <= sr < N and 0 <= sc < N:
                        if matrix[sr][sc] != "visited" and matrix[sr][sc] == value:
                            matrix[sr][sc] = "visited"
                            stack.append((sr, sc))
                            temp += 1

            answer = max(temp, answer)

print(answer)

---

 

 

모래섬

1초마다 물이 상하좌우로 찬다

즉 상하좌우로 1이 0이 되는 것이다

섬이 2개 이상일 때까지 기다리거나, 아예 없어질 때까지 초를 세는 것이다

물이 차오르는 함수

 

물이 차오르고 난 후, 섬이 몇 개인지 알려주는 함수

 

위의 두 함수들을 계속 반복하면서, 섬이 2개 이상이 나오는지 또는 섬이 아예 없어지는지 확인하면서 while문을 순회하면 된다

from copy import deepcopy

def increase_water(water):
    temp_water = []

    for row, column in water:
        for j in range(4):
            sr, sc = dr[j] + row, dc[j] + column

            if 0 <= sr < N and 0 <= sc < M:
                if island[sr][sc] == 1:
                    island[sr][sc] = 0
                    temp_water.append((sr, sc))

    return temp_water

def valid_island():
    temp_island = deepcopy(island)
    island_count = 0
    flag = "One Island"

    for i in range(N):
        for j in range(M):

            if island[i][j] == 1 and temp_island[i][j] == 1:
                stack = [(i, j)]
                temp_island[i][j] = "visited"
                island_count += 1

                while stack:
                    row, column = stack.pop()

                    for k in range(4):
                        sr, sc = dr[k] + row, dc[k] + column

                        if 0 <= sr < N and 0 <= sc < M:
                            if temp_island[sr][sc] == 1 and island[sr][sc] == 1:
                                temp_island[sr][sc] = "visited"
                                stack.append((sr, sc))

    if island_count == 0:
        flag = "No More Island"
        return flag
    elif island_count == 1:
        return flag
    else:
        flag = "Can Build Bridge"
        return flag



dr, dc = [-1, 0, 0, 1], [0, -1, 1, 0]
N, M = map(int, input().split())
island = [list(map(int, input().split())) for _ in range(N)]

water, cnt = [], 0

for i in range(N):
    for j in range(M):
        if island[i][j] == 0:
            water.append((i, j))


while True:
    if valid_island() == "One Island":
        water = increase_water(water)
        cnt += 1

    elif valid_island() == "No More Island":
        print("-1")
        break

    elif valid_island() == "Can Build Bridge":
        print(cnt)
        break