ebson

#풀이1 인구 이동 플래그를 사용하지 않고 풀이하여 일부 케이스에서만 통과했다. 정답 풀이 참고해 인구 이동 플래그 사용하는 풀이로 제출한 결과 성공했다. from collections import deque N, L, R = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] dy = (0, 0, 1, -1) dx = (1, -1, 0, 0) def bfs(y, x): dq = deque() dq.append((y, x)) unite_country_set = set() while dq: (y, x) = dq.popleft() unite_country_set.add((y, x)) chk[y][x] += ..

방문체크 배열에 소요시간 정보를 저장하는 방식으로 bfs 구현해 풀이한 결과 성공했다. 주의 : 방문체크 배열 크기는 최대+1 이어야 인덱스 오류나지 않는다. N, K = map(int, input().split()) from collections import deque chk = [-1] * 100_001 chk[N] = 0 def bfs(): dq = deque() dq.append(N) while dq: cur = dq.popleft() if chk[K] != -1: return chk[K] if 0

#풀이1 bfs 방식으로 각 사람사이 최단거리를 구하고 그 합을 리스트에 저장해 합계, 사람번호 오름차순으로 정렬해 첫번째 사람의 번호를 출력 N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(M)] from collections import deque def bfs(n): dq = deque() dq.append(n) while dq: cur = dq.popleft() if cur == n and adj[n-1][n-1] == 1 : break adj[n-1][n-1] = 1 for i in range(M): if board[i][0] == cur and not adj[n-1][board[i][..

1. 아기상어 최초 위치 찾기 2 먹을 수 있는 상어가 없을 때가지 아래를 반복 3. bfs 방식으로 현재 아기상어 크기로 먹을 수 있는 상어 리스트 찾기 4. bfs 방식으로 찾은 먹은 상어 리스트를 거리 오름차순, 위, 왼쪽 순으로 정렬 5. 상어 먹은 cnt를 1 증가하고 현재 아기 상어 사이즈와 같으면 아기 상어 사이즈를 1 증가 6. 먹은 상어 리스트의 첫번째 상어 좌표의 값을 0으로 저장 7. 먹은 상어 리스트의 첫번째 상어까지 거리를 ans 값에 더하기 8. 먹은 상어 리스트의 크기가 0이면 ans 값을 출력 bfs 내부에서 대부분 처리하려고 풀이한 결과 일부 테스트 케이스에서만 통과했다. 정답 풀이 참고해 위 순서로 풀이해 성공했다. N = int(input()) board = [list(..

1. 직사각형 위 모든 좌표를 저장 2. 직사각형이 아닌 부분을 bfs 방식으로 탐색 3. 방문체크 사용하고 bfs 내부에서 탐색 영역 크기 저장해 반환 4. 영역 개수, 영역 크기 출력 위 순서로 bfs 사용하여 풀이할 수 있다. M, N, K = map(int, input().split()) graph = [[0]*N for _ in range(M)] for _ in range(K): (x1, y1, x2, y2) = map(int, input().split()) for cy in range(y1, y2): for cx in range(x1, x2): graph[cy][cx] += 1 dy = (0, 0, -1, 1) dx = (-1, 1, 0, 0) from collections import deq..

플로이드 워셜 알고리즘을 활용하여 풀 수 있다. N = int(input()) graph = [list(map(int, input().split())) for _ in range(N)] for k in range(N): for s in range(N): for e in range(N): if graph[s][k] == 1 and graph[k][e] == 1: graph[s][e] = 1 for row in graph: print(*row)

벽을 부수는 모든 경우의 수를 구하고 bfs를 여러번 돌려서 풀이한 결과 테스트 케이스에서는 통과했으나 전체 테스트 케이스에서 시간 초과 되었다. 정답 풀이 참고해 방문체크시 벽 부수기 기회 사용여부를 함께 저장하는 방식으로 bfs를 한번만 돌리도록 풀이한 결과 성공했다. N, M = map(int, input().split()) graph = [input() for _ in range(N)] visited = [[[0]*2 for _ in range(M)] for _ in range(N)] dy = (0, 0, -1, 1) dx = (-1, 1, 0, 0) from collections import deque def bfs(): dq = deque() dq.append((0, 0, 1, 1)) visi..

1. 체스판에서 나이트가 움직일 수 있는 8개 좌표 저장 2. bfs 방식으로 출발 좌표에서 도착 좌표로 가는 횟수 계산 풀이1) 그래프를 방문체크 배열로 사용하면서 카운트하거나 풀이2) deque에서 카운트 #풀이1 - 그래프(방문체크 배열)에 움직인 횟수를 저장 from collections import deque dx = (1, 1, -1, -1, 2, 2, -2, -2) dy = (2, -2, 2, -2, 1, -1, 1, -1) def bfs(x1, y1, x2, y2, I): if (x1, y1) == (x2, y2): return 0 dq = deque() dq.append((x1, y1)) board = [[0]*I for _ in range(I)] board[x1][y1] = 1 whil..