2583 영역 구하기 / DFS, BFS
정답정사각형 범위의 좌표들은 모두 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] = 12차원 배열을 돌릴 때는 y값과 x값을 잘 생각하며 돌려야 함from collections import dequem, n, k = map(int, input().split()) # m = 높이, n = 가로 길이# 그래프 세..
2667 단지번호붙이기 / DFS, BFS
정답방문한 지점은 다시 방문할 수 없도록 해당 좌표의 값을 1로 변경해야 함큐에서 해당 노드를 뺄 때는 while문 아래에서 빼야 함from collections import dequen = 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..
1389 케빈 베이컨의 6단계 법칙 / DFS, BFS
선택해야하는 알고리즘최단거리 = BFSBFS는 가까운 노드부터 탐색하기 때문에 첫 방문 = 최단거리임이 보장됨미로 탈출 (1칸 이동이 비용 1일 때)각 노드까지 몇 단계만에 갈 수 있는지최단 이동 횟수, 최단 거리 찾기모든 경로를 다 탐색하고 싶을 때 = DFS모든 경로를 다 탐색하고 싶을 때모든 경우의 수를 보고 싶을 때 (조합, 순열, 경로)백트래킹 (N-Queen, 스도쿠, 조합 등)사이클 찾기=> 그러므로 해당 문제에서는 반드시 BFS를 사용해야 함 기준 노드에서부터 다른 노드까지의 거리1. distance = [0] * (n + 1) 의미모든 거리를 처음엔 0으로 초기화 n = 5distance = [0] * (n + 1)print(distance)# 출력: [0, 0, 0, 0, 0, 0]#..
1260 DFS와 BFS / DFS, BFS
정답from collections import dequedef 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) ..
11724 연결 요소의 개수 / DFS, BFS
인접리스트 만들기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 vi..
