2468 안전 영역 / DFS, BFS
정답그래프 깊은 복사g = [row[:] for row in graph] 아무런 땅이 물에 젖지 않는 경우도 포함해야 하기 때문에 비가 오는 경우를 0부터 넣어서 체크해야 함 (1부터 시작하면 1이하의 땅은 젖기 때문에)from collections import dequen = int(input()) # n * n 지도# 지도 세팅graph = []for _ in range(n): row = input() row_list = list(map(int, row.split())) graph.append(row_list)# 상하좌우 세팅dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def BFS(x, y, g): queue = deque() queue.append((..
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]#..
