기록

정답

• 정사각형 범위의 좌표들은 모두 1로 마킹하고 해당 그래프에서 1이 아닌 부분만 탐색하면 됨
• 셀의 경계 좌표이기 때문에 실제로 색칠되는 칸은 이차원배열에서 돌아가는 것처럼 생각하면 됨

# 입력받은 정사각형 좌표들을 1로 마킹
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())

    for y in range(y1, y2):
        for x in range(x1, x2):
            graph[y][x] = 1

• 2차원 배열을 돌릴 때는 y값과 x값을 잘 생각하며 돌려야 함

from collections import deque
m, n, k = map(int, input().split()) # m = 높이, n = 가로 길이

# 그래프 세팅
graph = []
for _ in range(m):
    row = []
    for _ in range(n):
        row.append(0)
    graph.append(row)

# 입력받은 정사각형 좌표들을 1로 마킹
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())

    for y in range(y1, y2):
        for x in range(x1, x2):
            graph[y][x] = 1

# 상하좌우 세팅
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 0인 부분만 그래프 탐색 시작
def BFS(y, x):
    queue = deque()
    queue.append((y, x))
    # 얘도 방문했기 때문에 1로 변경해줘야 함
    graph[y][x] = 1
    count = 1

    while queue:
        y1, x1 = queue.popleft()
        for i in range(4):
            nx = x1 + dx[i]
            ny = y1 + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if graph[ny][nx] == 1:
                continue
            if graph[ny][nx] == 0:
                queue.append((ny, nx))
                graph[ny][nx] = 1
                count = count + 1

    return count

distance = []
ans = 0

for y in range(m):
    for x in range(n):
        if graph[y][x] == 0:
            ans = ans + 1
            distance.append(BFS(y, x))

distance.sort()
print(ans)
for i in distance:
    print(i, end=" ")

정답

• 방문한 지점은 다시 방문할 수 없도록 해당 좌표의 값을 1로 변경해야 함
• 큐에서 해당 노드를 뺄 때는 while문 아래에서 빼야 함

from collections import deque
n = int(input()) # n * n 형태의 지도의 크기

# 지도 세팅
maze = []
for _ in range(n):
    row = input()
    char_row = list(row)
    int_row = list(map(int, char_row))
    maze.append(int_row)

# 상하좌우 좌표 세팅
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def BFS(x, y):
    queue = deque()
    queue.append((x, y))
    maze[x][y] = 0
    count = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위가 안되면 skip
            if nx >= n or ny >= n or nx < 0 or ny < 0:
                continue

            # 0 이라면 skip
            if maze[nx][ny] == 0:
                continue

            # 탐색 할 수 있는 범위라면 count 증가
            if maze[nx][ny] == 1:
                queue.append((nx, ny))
                maze[nx][ny] = 0 # 방문한 지점은 다시 재방문 할 수 없도록 0으로 변경
                count = count + 1

    return count

aprt = []
ans = 0

# 지도 탐색 시작
for i in range(n):
    for j in range(n):
        if maze[i][j] == 1:
            aprt.append(BFS(i, j))
            ans = ans + 1

aprt.sort()
print(ans)
for i in aprt:
    print(i)

BFS로 풀기

• 해당 도착지로 가기 위해 지나야하는 최소의 칸 수를 구해야하므로 DFS, BFS 중에서 BFS로 풀어야겠다는 생각을 가져야 함

2차원 미로 배열 만들기

• 어떤 문자열에 list() 함수를 사용하면 해당 문자열은 리스트로 변환됨
• 변환된 리스트는 문자열이기 때문에 숫자로 변경해줘야 함
• N × M 크기의 배열로 표현되는 미로이므로 for문의 range는 n

n, m = map(int, input().split()) # N × M 크기의 배열로 표현되는 미로, N개의 줄에 M개의 정수로 미로가 주어짐
maze = []

# 2차원 배열 만들기
for _ in range(n):
    row = input()
    row_list = list(row) # ['1', '0', '1', '0' ...]
    int_list = list(map(int, row_list)) # [1, 0, 1, 0 ...]
    maze.append(int_list)

미로에서 상, 하, 좌, 우로 움직여야하는 경우의 수 세팅

• (1, 1)에서 위로 움직인다면? : (0, 1) => x축은 유지하고 y축에서 +1을 해야 함 dx = 0, dy = 1

# 상하좌우 방향
# x축과 y축을 움직이는 조합 : 왼쪽으로 움직이는 경우, 오른쪽으로 움직이는 경우, 아래로 가는 경우, 위로 가는 경우
# delta x : x 축 방향으로의 변화량
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

정답

from collections import deque

n, m = map(int, input().split()) # N × M 크기의 배열로 표현되는 미로, N개의 줄에 M개의 정수로 미로가 주어짐
maze = []

# 2차원 배열 만들기
for _ in range(n):
    row = input()
    row_list = list(row) # ['1', '0', '1', '0' ...]
    int_list = list(map(int, row_list)) # [1, 0, 1, 0 ...]
    maze.append(int_list)

# 상하좌우 방향
# x축과 y축을 움직이는 조합 : 왼쪽으로 움직이는 경우, 오른쪽으로 움직이는 경우, 아래로 가는 경우, 위로 가는 경우
# delta x : x 축 방향으로의 변화량
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def BFS(x, y):
    queue = deque()
    queue.append((x, y)) # 시작은 0,0

    while queue:
        x, y = queue.popleft()

        # 시작 좌표에서부터 상, 하, 좌, 우로 움직이는 경우
        for i in range(4):
            # next x : 다음 x 좌표, 한칸 이동한 좌표
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 벗어나면 skip
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            # 이동할 수 없는 칸이면 skip
            if maze[nx][ny] == 0:
                continue
            # 처음 방문하는 길이면 현재까지의 거리 + 1
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))

    return maze[n-1][m-1]

print(BFS(0, 0))

정답

• 어제 풀었던 케빈 베이컨의 법칙과 동일
• 시작 노드로부터 도착노드까지의 거리를 구해서 반환하면 됨

from collections import deque

def BFS (graph, start, n, goal):
    queue = deque()
    queue.append(start)
    visited = [False] * (n + 1)
    visited[start] = True
    distance = [0] * (n + 1)

    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if visited[neighbor] is False:
                distance[neighbor] = distance[current] + 1
                queue.append(neighbor)
                visited[neighbor] = True

                # 방문한 노드가 목표 노드라면 시작점노드로부터의 거리 반환
                if neighbor == goal:
                    return distance[neighbor]

    # 목표 노드에 방문하지 않았다면 -1 함수가 모두 종료되고 -1 반환
    return -1

n = int(input()) # 전체 사람의 수 (노드 수)
x, y = map(int, input().split()) # 촌수를 계산해야 하는 서로 다른 두 사람의 번호
m = int(input()) # 부모, 자식간의 관계의 수 (간선 수)
con = []
for _ in range(m):
    a, b = map(int, input().split())
    con.append((a, b))

graph = []
for _ in range(n + 1):
    graph.append([])

for a, b in con:
    graph[a].append(b)
    graph[b].append(a)

print(BFS(graph, x, n, y))

선택해야하는 알고리즘

최단거리 = BFS

• BFS는 가까운 노드부터 탐색하기 때문에 첫 방문 = 최단거리임이 보장됨
• 미로 탈출 (1칸 이동이 비용 1일 때)
• 각 노드까지 몇 단계만에 갈 수 있는지
• 최단 이동 횟수, 최단 거리 찾기

모든 경로를 다 탐색하고 싶을 때 = DFS

• 모든 경로를 다 탐색하고 싶을 때
• 모든 경우의 수를 보고 싶을 때 (조합, 순열, 경로)
• 백트래킹 (N-Queen, 스도쿠, 조합 등)
• 사이클 찾기

=> 그러므로 해당 문제에서는 반드시 BFS를 사용해야 함

기준 노드에서부터 다른 노드까지의 거리

1. distance = [0] * (n + 1) 의미

• 모든 거리를 처음엔 0으로 초기화

n = 5
distance = [0] * (n + 1)
print(distance)
# 출력: [0, 0, 0, 0, 0, 0]
# 인덱스:  0  1  2  3  4  5

 2. distance[i] = distance[current] + 1 

• current는 지금 방문 중인 노드
• i는 current와 연결된 이웃 노드
• 시작 노드가 1
• current = 1 일 때, i = 2 라면
  • 1번에서 2번까지 가는 거리 = distance[1] + 1 = 0 + 1 = 1

distance[i] = distance[current] + 1

-> 이렇게 하면, BFS 특성상 최단 거리가 자동으로 계산됨

정답

from collections import deque

def BFS(graph, start, n):
    queue = deque()
    queue.append(start)
    visited = [False] * (n + 1)
    distance = [0] * (n + 1) # [0, 0, 0, 0, 0, ...], 해당 노드 기준으로 나머지 노드까지의 최단 거리, distance = [0, 0, 1, 2, 1]
    visited[start] = True # "1번 노드 기준으로 각 노드까지의 최단거리"

    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if visited[neighbor] is False:
                queue.append(neighbor)
                distance[neighbor] = distance[current] + 1
                visited[neighbor] = True

    return sum(distance[1:])

n, m = map(int, input().split()) # 정점의 수, 간선의 수
con = []
for _ in range(m):
    a, b = map(int, input().split())
    con.append((a, b))

graph = []
for _ in range(n + 1):
    graph.append([])

for a, b in con:
    graph[a].append(b)
    graph[b].append(a)

ans = []
min_score = 100 # 가장 무한대로 큰 수
for i in range(1, n + 1):
    score = BFS(graph, i, n)
    if score < min_score:
        min_score = score
        ans = [i]
    elif score == min_score:
        ans.append(i)

ans.sort()
print(ans[0])

정답

def DFS(g, start, visited):
    visited[start] = True

    for i in g[start]:
        if visited[i] is False:
            DFS(g, i, visited)

t = int(input())
ans_arr = []

for i in range(t):

    n = int(input())
    graph = []
    for _ in range(n + 1):
        graph.append([])

    v = list(map(int, input().split()))
    for i in range(1, n + 1):
        graph[i].append(v[i - 1])

    visited = [False] * (n + 1)
    ans = 0

    for i in range(1, n + 1):
        if visited[i] is False:
            DFS(graph, i, visited)
            ans = ans + 1

    ans_arr.append(ans)

for i in ans_arr:
    print(i)

정답

from collections import deque
def DFS(graph, start, visited, dfs_ans):
    visited[start] = True
    dfs_ans.append(start)

    for i in graph[start]:
        if visited[i] is False:
            DFS(graph, i, visited, dfs_ans)

def BFS(graph, start, visited, bfs_ans):
    queue = deque()
    queue.append(start)
    visited[start] = True
    while queue:
        v = queue.popleft()
        bfs_ans.append(v)
        for i in graph[v]:
            if visited[i] is False:
                queue.append(i)
                visited[i] = True

n, m, v = map(int, input().split())
con = []
for _ in range(m):
    a, b = map(int, input().split())
    con.append((a, b))

graph = []
for i in range(n+1):
    graph.append([])

for a, b in con:
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort()

dfs_visited = [False] * (n + 1)
bfs_visited = [False] * (n + 1)
dfs_ans = []
bfs_ans = []

DFS(graph, v, dfs_visited, dfs_ans)
BFS(graph, v, bfs_visited, bfs_ans)

for i in dfs_ans:
    print(i, end=" ")

print()
for i in bfs_ans:
    print(i, end=" ")

인접리스트 만들기

n, m = map(int, input().split()) # 정점, 간선의 개수

con = []
for i in range(m):
    a, b = map(int, input().split())
    con.append((a,b))

# 그래프 세팅, 이차원 리스트로 만들기
graph = []
for i in range(0, n + 1):
    graph.append([])

for a, b in con:
    graph[a].append(b)
    graph[b].append(a)

정답

def DFS(graph, start, visited):
    visited[start]= True
    # print(start, end=' ')
    for i in graph[start]:
        if visited[i] is False:
            visited[i] = True
            DFS(graph, i, visited)

n, m = map(int, input().split()) # 정점, 간선의 개수

con = []
for i in range(m):
    a, b = map(int, input().split())
    con.append((a,b))

# 그래프 세팅, 이차원 리스트로 만들기
graph = []
for i in range(0, n + 1):
    graph.append([])

for a, b in con:
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (n + 1)
# print(graph)
ans = 0

# visited에서 0을 제외한 나머지 인덱스의 값이 true가 될 때까지 반복
for i in range(1, n + 1):
    if visited[i] is False:
        ans = ans + 1
        DFS(graph, i, visited)

# print(visited)
print(ans)