ebson

dfs으로 풀이 시도했으나 시간초과 났고, 시간초과가 나지 않더라도 테스트 케이스 범위로 인해 순환함수 호출 최대 제한에 걸릴 수 밖에 없다. bfs 방식으로 탐색하고 PyPy3으로 제출해야 한다. 시간초과난 dfs 풀이 import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] for i in range(M): (e, s) = map(int, input().split()) graph[s].append(e) def dfs(node): global cnt for nxt in graph[node]: if not visited[n..

1. 도화지의 모든 좌표를 순회하면서 아래를 반복 1.1. 체크되지 않은 좌표이고 좌표 값이 1이면, 합계 리스트에 해당 좌표를 인자로 아래와 같이 bfs한 결과를 저장 1.1.1. deque에 인자로 받은 좌표값을 저장 1.1.2. tot을 1로 초기화 1.1.3. 체크배열의 해당 좌표값을 1로 갱신 1.1.4. dq가 빌 때까지 반복 1.1.4.1. 상하좌우 좌표에 대해 도화지에 존재하는 좌표이고, 좌표값이 1이고, 체크배열의 값이 0이면, dq에 추가하고 chk배열의 값을 1로 갱신하고 tot을 1 증감 1.1.5. tot 값을 반환 2. tot_list의 길이를 출력 3. tot_list의 길이가 0보다 크면 최대값을 출력하고 0이면 0을 출력 N, M = map(int, input().split..

1. dp 배열을 대나무숲 그래프의 크기만큼의 -1으로 초기화 2. dfs 함수를 다음과 같이 정의 2.1. y, x좌표를 인자로 받고 dp[y][x]값이 -1이면 0으로 갱신 후 아래를 수행 2.1.1. 상하좌우 좌표에 대해 유효한 좌표인지 검사하고 현재 좌표값보다 더 큰 값이면 dp[y][x]에서 dfs[ny][nx]값과 dp[y][x]값 중 더 큰값으로 갱신 2.2. dp[y][x]+1한 값을 반환 3. 대나무숲의 모든 좌표를 순회하면서 dfs(y, x)한 값의 최대값을 저장하고 출력 N = int(input()) graph = [list(map(int, input().split())) for _ in range(N)] dy = (-1, 1, 0, 0) dx = (0, 0, -1, 1) import..

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