ebson

1. 인덱스를 노드 번호로 갖고 연결 노드와 그 거리쌍을 요소로 갖는 그래프를 초기화 2. 인덱스를 노드 번호로 갖고 요소를 누적 거리값으로 갖는 방문체크 배열을 -1으로 초기화 3. 노드 번호와 누적 거리값을 인자로 받고 연결 노드를 탐색하는 dfs 함수 정의 4. 트리의 루트 노드에서 가장 먼 거리에 있는 노드번호 찾기 5. 4번에서 찾은 노드로부터 dfs 결과 누적거리값 중 최대값을 출력 import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline N = int(input()) graph = [[] for _ in range(N+1)] for _ in range(N): I = list(map(int, input().split())) s, e..

1. 그래프 행렬 초기화 2. 인접한 노드에 대해 순환호출하되 거리 누적해 전달하는 dfs 함수 정의 3. 인접행렬 순회하면서 dfs 호출하고 최대 거리 저장 4. 최대 거리 리스트에서 최댓값 출력 문제에 제시된 테스트 케이스는 통과했으나 제출 시 메모리 초과했다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N = int(input()) adj = [list(map(int, input().split())) for _ in range(N-1)] graph = [[0] * N for _ in range(N)] for (y, x, d) in adj: graph[y-1][x-1] = d graph[x-1][y-1] = d def dfs..

1. 한 해가 지난 후 빙산 그래프 결과를 저장하고 0이 아닌 좌표를 ice_set에 저장 2. ice_set 을 순회하면서 방문체크하지 않은 좌표만을 대상으로 dfs를 수행, dfs 횟수를 저장 3. dfs 횟수가 2회 이상이면 year_cnt를 출력, 빙산 그래프에 얼음이 없으면 0을 출력 N, M = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(N)] dy = (1, -1, 0, 0) dx = (0, 0, 1, -1) def year_after(graph): temp = [g[:] for g in graph] for gy in range(1, N-1): for gx in range(1, M-1): ..

시작노드를 인덱스로 하고 인접노드를 요소로 갖는 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

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