ebson

시작노드를 인덱스로 하고 인접노드를 요소로 갖는 1. graph 리스트와 이분 그래프 여부를 판단하는 2. 플래그 변수를 사용한 풀이이다. 3. sys.stdin.readline 으로 빠른 입력 받기를 사용해야 시간초과 나지 않는다. 풀이1 - DFS 활용 import sys sys.setrecursionlimit(10**6) N = int(input()) input = sys.stdin.readline def dfs(node): global flag for neighbor in graph[node]: if (visited[neighbor] == -1): visited[neighbor] = 1 if (visited[node] == 2) else 2 dfs(neighbor) else: if visited[..

1. 방문한 좌표의 알파벳을 중복 제거해 저장할 set 자료형 변수 초기화 2. 그래프 순회하면서 방문하지 않은 알파벳이면 set 자료형 변수에 저장하고 dfs 후 삭제 3. 매 dfs 마다 최대 거리수를 저장 4. 최대 거리수 출력 R, C = map(int, input().split()) graph = [list(input().strip()) for _ in range(R)] visited = set(graph[0][0]) max_d = 1 dy = (-1, 1, 0, 0) dx = (0, 0, -1, 1) def dfs(y, x, d): global max_d max_d = max(max_d, d) for i in range(4): ny = y + dy[i] nx = x + dx[i] if 0

dfs + dp 1. 그래프와 동일한 크기로 dp테이블을 -1으로 초기화 2. dfs 내부에서 dp 테이블에 저장된 좌표면 저장된 값을 반환 3. 맨 오른쪽 맨 아래 좌표이면 1을 반환 4. 2, 3에 해당하지 않으면 처음 방문하는 좌표이므로 dp 테이블에 0을 저장 5. 상하좌우 검사해 현재 좌표에 저장된 값보다 작으면 dfs에 해당좌표를 인자로 재귀호출한 결과를 dp 테이블에 저장 6. dfs에 전달된 좌표에 해당하는 dp테이블 값을 반환 M, N = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(M)] dp = [[-1]*N for _ in range(M)] import sys sys.setrecur..

#풀이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..