7562 나이트의 이동 / DFS, BFS
정답나이트가 이동할 수 있는 경우의 수를 처음에 아래와 같이 했더니 오답이 나옴 dx = [-1, 1, 1, 2, -1, -2, 2, 1] dy = [2, -2, 2, 1, -2, -1, -1, -2] 다른 정답들을 찾아봐도 이해할 수 가 없어서 시계방향대로 이동할 수 있는 경로를 바꿨더니 정답이 나옴 dx = [-2, -1, 1, 2, 2, 1, -1, -2] dy = [1, 2, 2, 1, -1, -2, -2, -1] BFS에서 최단 경로 문제를 풀 땐 또는 방향 순서를 안정된 기준(예: 시계 방향) 으로 맞춰줘야 함from collections import dequecase = int(input())ans = []for _ in range(case): n = int(inp..
5014 스타트링크 / DFS, BFS
정답숨바꼭질이랑 비슷한 문제하나의 그래프에서 최소거리로 탐색한다고 보면 됨from collections import dequef, s, g, u, d = map(int, input().split()) # 건물의 총 수, 현재 위치, 회사 위치, 위로 u층, 아래로 d층distance = [0] * (f + 1)visited = [False] * (f + 1)def BFS(s): queue = deque() queue.append(s) visited[s] = True while queue: current = queue.popleft() if current == g: return distance[current] for next i..
1926 그림 / DFS, BFS
정답from collections import dequen, m = map(int, input().split()) # 세로 크기(높이), 가로 크기graph = []for _ in range(n): row = list(map(int, input().split())) graph.append(row)# 상하좌우 세팅dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def BFS(y, x): queue = deque() queue.append((y, x)) graph[y][x] = 0 count = 1 while queue: y, x = queue.popleft() for i in range(4): nx = x +..
1012 유기농 배추 / DFS, BFS
정답from collections import dequet = int(input())ans = []for i in range(t): m, n, c = map(int, input().split()) # 배추밭 가로길이, 세로길이, 배추가 심어져 있는 개수 # 배추밭 세팅 graph = [] for _ in range(n): row = [0] * m graph.append(row) for _ in range(c): x, y = map(int, input().split()) graph[y][x] = 1 # 상하좌우 세팅 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def BFS(y, x):..
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((..
