ebson

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..

1. 3차원 배열로 토마토 정보 초기화 2. 방문체크용 3차원 배열을 초기화 3. 익은 토마토 좌표를 저장하고 방문체크좌표값에 +1 4. 인접한 6개 토마토를 익힌 결과를 bfs방식으로 저장 5. 안익은 토마토가 있는경우 -1 출력, 없다면 방문체크좌표값에 저장된 최대값-1을 출력 M, N, H = map(int, input().split()) graph = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)] visited = [[[0]*(M) for _ in range(N)] for _ in range(H)] dz = (0, 0, 0, 0, -1, 1) dy = (-1, 1, 0, 0, 0, 0) dx = (0, 0, -1, ..

1.bfs방식으로 좌표를 모두 탐색하되 영역색상별로 탐색 2. 비색약자인 경우, 적록색약자인 경우 각각 탐색 3. 각각의 경우의 영역의 총 개수를 출력 N = int(input()) graph = [input() for _ in range(N)] dy = (-1, 1, 0, 0) dx = (0, 0, -1, 1) from collections import deque def bfs(y, x, rgb): dq = deque() dq.append((y, x)) while dq: (cy, cx) = dq.popleft() for i in range(4): ny = cy + dy[i] nx = cx + dx[i] if rgb == 'RG': if 0

1. 벽을 세울 수 있는 3개 좌표 추출하는 모든 경우에 대해 아래 2, 3 반복 2. bfs 방식으로 벽을 세운 후 전염결과 구하기 3. 전염후 안전지대 총 개수 계산 4. 안전지대 총 개수의 최대값을 출력 N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] space = [] infected = [] for y in range(N): for x in range(M): if board[y][x] == 0: space.append((y, x)) if board[y][x] == 2: infected.append((y, x)) dy = (0, 0, -1, 1) dx = (-1, 1, 0, 0) ..