Algorithm(BOJ, Python)/BFS&DFS25 [백준_7576] 토마토 python 오늘 배운 점 : bfs 동시에 돌릴 수 있다. (좌표를 다 큐에 때려놓고 시작하면 된다.) # m, n 입력 m, n = map(int, input().split()) # storage storage = [ list(map(int, input().split())) for _ in range(n) ] # in_range(x, y): def in_range(x, y): return 0 2022. 8. 18. [백준_10026] 적록색약 python 처음 이 문제를 풀었을 때, 런타임 에러가 떴다. 테스트 케이스는 통과했는데 런타임 에러가 뜨는 경우는, 인덱스 설정을 잘못 했을 경우가 많다는 것을 경험적으로 알고 있었기에, 여기저기 찾아봤지만 아무리 찾아봐도 잘못된 점이 없었다. 그러던 중 n이 100까지 갈 수 있다는 것을 알게 되었고, 혹시 최대 리커젼 가능 횟수에 걸린 것이 아닐까 하는 생각이 들었다. 파이썬은 최대 리커젼 가능 횟수가 1000회로 디폴트값이 설정되어있기 때문에, 이 이상의 재귀를 돌릴라면, 이를 인위적으로 바꿔주는 코드가 필요하다. 역시나, 이를 바꿔주니 해결되었다. # n 입력 n = int(input()) # grid 설계 grid = [ [0] * n for _ in range(n) ] # grid 채워넣기 for i i.. 2022. 8. 16. [백준_14502] 연구소 python 오늘 배운 점은, 조합을 구하는 재귀를 돌릴 때, 보다 빠른 방법을 찾았다는 것이다. # 입력 속도 개선 import sys input = sys.stdin.readline # n, m 입력 n, m = map(int, input().split()) # lab lab = [ list(map(int, input().split())) for _ in range(n) ] # visited visited = [ [0] * m for _ in range(n) ] # in_range(x, y) def in_range(x, y): return 0 비어있는 공간의 좌표를 기록해줄 리스트 empty_pos = [] # 연구실을 돌면서 for i in range(n): for j in range(m): # 빈 공간을 찾으.. 2022. 8. 15. [백준_7562] 나이트의 이동 python 최소 경로를 탐색해야 하는 문제이므로, dfs가 아닌 bfs를 사용해야 한다. 경로는 step배열을 이용하여 구한다. # 큐 사용 위한 준비 from collections import deque # t 입력 t = int(input()) # n 입력 for _ in range(t): n = int(input()) # 시작 위치 입력 s_x, s_y = map(int, input().split()) # 종료 위치 입력 e_x, e_y = map(int, input().split()) # grid grid = [ [0] * n for _ in range(n) ] # visited visited = [ [0] * n for _ in range(n) ] # step step = [ [0] * n for _ in.. 2022. 8. 13. [백준_2178] 미로탐색 python 경로를 찾는 데에 bfs를 사용하든 dfs를 사용하든 자기 맘이다. 더 자신있는 것을 사용하는 쪽이 좋다. 그러나 최소 경로를 찾을 때에는 bfs를 사용해야 한다. # n, m 입력 n, m = map(int, input().split()) # maze maze = [ [0] * m for _ in range(n) ] # maze 채우기 for i in range(n): # block 입력받기 block = input() for j in range(len(block)): # 이동할 수 있는 칸은 if block[j] == '1': # 1로 표시 maze[i][j] = 1 # visited visited = [ [0] * m for _ in range(n) ] # step step = [ [0] * m f.. 2022. 8. 12. [백준_2667] 단지번호붙이기 python 입력 형식에서 띄어쓰기 기준으로 입력을 받으면 큰일난다. 각 줄을 문자열로 입력받아. 이를 정수형으로바꿔 다시 하나하나 넣어주는 과정이 필요하다. # n 입력 n = int(input()) # grid grid = [ [0] * n for _ in range(n) ] # grid 채워넣기 for i in range(n): towns = input() for j in range(len(towns)): grid[i][j] = int(towns[j]) # visited visited = [ [0] * n for _ in range(n) ] # in_range(x, y) def in_range(x, y): return 0 2022. 8. 11. [백준_1260] DFS와BFS python 오늘 코테 캠프에서 배운 내용이였다. 복습하기에 안성맞춤인 문제였다. 중요 포인트를 정리해보자면, DFS와 BFS를 코테에서 사용할 때는 둘 중 자신있는 것을 사용하면 된다. n이 1000을 넘지 않는 경우에는 2차원 배열로 이를 구현하는 것이 좋으며, 넘을 경우에는 인접 리스트로 이를 구현하는 쪽이 메모리 측면에서 유리하다. DFS는 재귀를 이용해, BFS는 큐(Queue)를 이용하여 구현한다. 최단거리를 구할 때는 BFS와 step 배열을 사용한다. visited의 관리가 중요하다. BFS든 DFS든 먼저 초기 vertex를 호출해주고 시작하는것이 직관적이다. (실수할 가능성이 줄어든다) # n, m, v 입력 n, m, v = map(int, input().split()) # starts, ends.. 2022. 8. 10. 이전 1 2 다음
