프로그래밍 공부131 구현_뱀 * 완전탐색 -> BFS/DFS 활용 - 모든 경우의 수 다 계산 [반복문, 재귀함수] * 시뮬레이션 -> 순열, 조합 라이브러리 (from itertools import permutations/combinations) n = int(input()) k = int(input()) data = [[0] * (n + 1) for _ in range(n + 1)] # 맵 정보 info = [] # 방향 회전 정보 # 맵 정보(사과 있는 곳은 1로 표시) for _ in range(k): a, b = map(int, input().split()) data[a][b] = 1 # 방향 회전 정보 입력 l = int(input()) for _ in range(l): x, c = input().split() info... 2022. 10. 8. DFS/BFS_감시 피하기 * 시뮬레이션 -> 순열, 조합 라이브러리 활용 * 조합 활용 -> from itertools import combinations from itertools import combinations n = int(input()) # 복도의 크기 board = [] # 복도 정보 (N x N) teachers = [] # 모든 선생님 위치 정보 spaces = [] # 모든 빈 공간 위치 정보 for i in range(n): board.append(list(input().split())) for j in range(n): # 선생님이 존재하는 위치 저장 if board[i][j] == 'T': teachers.append((i, j)) # 장애물을 설치할 수 있는 (빈 공간) 위치 저장 if board[i][.. 2022. 10. 8. BFS/DFS_아기상어(삼성기출) * 완전탐색 -> BFS/DFS 활용 (반복문, 재귀함수) 문제 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램 작성 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹.. 2022. 10. 8. 플로이드 워셜, 다익스트라 알고리즘 플로이드 워셜 알고리즘 # 점화식에 따라 플로이드 워셜 알고리즘을 수행 for k in range(1, n + 1): for a in range(1, n + 1): for b in range(1, n + 1): graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다 플로이드 워셜 알고리즘은 다이나믹 프로그.. 2022. 10. 8. 이전 1 2 3 4 5 6 7 ··· 33 다음
