ebson

플로이드 워셜 알고리즘을 활용하여 풀 수 있다. 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) ..

방문체크하면서 bfs 방식으로 카운팅하여 K에 도달하는 최소시간을 구할 수 있다. N, K = map(int, input().split()) from collections import deque def bfs(N): visited = [0] * 100001 visited[N] += 1 dq = deque() dq.append((N, 0)) while dq: (cur, cnt) = dq.popleft() if cur == K: return cnt for nxt in (cur*2, cur+1, cur-1): if 0

1. deque에 익은 토마토 좌표를 모두 저장 2. dfs 방식으로 deque를 검사하면서 상화좌우 안익은 토마토는 현재토마토 좌표의 값의 + 1의 값을 갖도록 저장 3. 익은 토마토로 변경된 토마토의 좌표를 deque에 저장 4. 전제 좌표 값을 순회하면서 0이 있으면 -1을 출력, 0이 없으면 좌표 값 중에서 최대-1을 출력 M, N = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] from collections import deque dq = deque() for y in range(N): for x in range(M): if board[y][x] == 1: dq.append((y, x))..