ebson

1. 인덱스 번호를 노드번호, 요소 값을 선택한 노드번호로 갖도록 choose 리스트를 N+1 길이로 초기화 2. chk 리스트를 N+1 개의 0으로 초기화 3. team 리스트를 생성 4. 1번부터 N번 노드까지 순회하면서 아래를 반복 4.1. chk[번호] 값이 0인지 검사 4.2. chk[번호] 값이 0이면, cycle 리스트를 초기화하고 dfs(번호)를 호출 4.2.1. dfs(번호)를 다음과 같이 실행 4.2.1.1. global team 변수를 선언, chk[번호]를 1 증감, cycle에 번호를 append, nxt에 choos(번호)를 저장 4.2.1.2. chk[nxt]가 1이면, cycle에 nxt가 있는지 검사하고 있으면 cycle에서 nxt가 처음 발견되는 index부터 마지막까지 ..

graph 를 하나 더 생성해 풀이하여 테스트 케이스 통과했으나 제출 시 실패했다. N = int(input()) parents = list(map(int, input().split())) delete = int(input()) graph = [[] for _ in range(N)] for i in range(1, N): graph[parents[i]].append(i) leaf_cnt = 0 def dfs(node): global leaf_cnt for child in graph[node]: if len(graph[child]) > 0: dfs(child) else: leaf_cnt +=1 dfs(0) leaf_cnt_0 = leaf_cnt leaf_cnt = 0 dfs(delete) if delete..

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

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