ebson

1. 모든 좌표를 순회하면서 아래를 반복1.1. 방문체크하고 집의 개수를 1으로 초기화한 후에 dfs를 수행1.1.1. 상하좌우 좌표값 중 값이 '1'이고 방문하지 않았으면 방문체크하고 dfs를 호출, 전역변수 d값을 1증감1.1.2. dfs함수 밖에서 초기화했던 d를 반환1.2. d_list에 dfs수행 결과 전역변수 d를 추가1.3. 영역의 개수 cnt를 1 증감2. 영역의 개수 cnt를 출력하고 d_list를 오름차순으로 출력 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { static int N, d, cnt; static int[][] board; ..

1. 아래와 같이 bfs방식으로 거리값을 증감하면서 좌표를 탐색하고 목적지에 도착한 경우 최단거리값을 출력1.1. 출발지 좌표와 초기 거리값을 Queue에 추가1.2. Queue 가 빌 때까지 아래를 반복1.2.1. Queue.poll 하여 현재좌표와 거리값을 저장1.2.2. 현재 좌표가 목적지 좌표이면 거리값을 반환1.2.3. 상하좌우 좌표를 검사하면서 좌표값이 '1'이고 방문하지 않은 경우 방문체크하고 Queue 에 좌표, 현재거리+1을 add2. bfs함수 호출 결과를 출력 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.u..

1. 첫번째 선거구의 조합을 모두 추출하고 아래를 반복 1.1. 첫번째 선거구의 조합과 그 외 나머지 선거구의 조합을 bfs, dfs 방식 중 하나로 순회해 가능한 조합인지 검사 1.2. 가능한 조합이라면 두 선거구의 인구수 차를 저장 2. 두 선거구의 인구수 차 중 최소값을 출력, 가능한 조합이 없으면 -1을 출력 N = int(input()) nums = [0] + list(map(int, input().split())) adj = [0] + [] for _ in range(N): adj.append(list(map(int, input().split()))[1:]) from collections import deque def bfs(nodes): dq = deque() dq.append(nodes[0..

dfs 방식으로 풀이 시도한 결과 테스트 케이스는 통과했지만 제출시 시간 초과 또는 메모리 초과가 발생했다. dfs 풀이(시간초과) N, M = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(N)] visited = [[False]*M for _ in range(N)] dy = (1, -1, 0, 0) dx = (0, 0, 1, -1) from collections import deque def bfs(y, x): dq = deque() dq.append((y, x)) while dq: (y, x) = dq.popleft() graph[y][x] = -2 for i in range(4): ny = y + ..

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. 인덱스 번호를 노드번호, 요소 값을 선택한 노드번호로 갖도록 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..