코테 탈출일지

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방식 - 트리 구조의 그래프에서 부모 노드를 확인하는 방법 고민 - bfs/dfs 탐색 방식 선택 코드 풀이 import sys input = sys.stdin.readline from collections import deque n = int(input()) graph = list([] for _ in range(n)) # 그래프의 연결 관계 저장할 리스트 parent = [0]*n # 각각의 노드의 parent를 조사해 저장할 리스트 visited =..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 접근 방식 - 고립된 영역 접근 방식 고민 - 방문 처리 방법 (visited 리스트 or 그래프 직접 표기) 및 시점 - count 시 코드 풀이 from collections import deque m, n, k = map(int, input().split()) # 세로 길이, 가로 길이, 정사각형 수 graph = [[0]*m for _ in range(n)] for _ ..

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 접근 방식 - 특이 조건 (중복 방문 가능) 처리 방식 고민 - 문제 이해 및 함수 선정 코드 풀이 import sys def dfs(node, cnt): # dfs 함수 구현 visited[node-1] = 1 # 방문 처리 for adj in range(1, n+1): # node의 인접 연결 노드 if visited[adj-1] == 0 and graph..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 접근 방식 - bfs/dfs 선택 - graph와 visited 리스트의 선언 여부 고민 - 촌수 count 시점 고민 코드 풀이 n = int(input()) graph = [[0]*n for _ in range(n)] # 연결 관계 표현 visited = [0]*n x, y = map(int, input().split()) info = int(input()) for _ in..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 접근 방식 - 함수 선정 (bfs, dfs) - 그래프 특정 좌표 방문 처리 방식 고민 - 적절한 count 시점 고민 코드 풀이 from collections import deque t = int(input()) # 몇 번의 테스트케이스인지 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] def bfs(graph, x, y): # bfs 함수 구현 q = deque() q.append([..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 접근 방식 - 그래프 탐색 방식 고민 코드 풀이 n = int(input()) # 컴퓨터의 수 k = int(input()) # 컴퓨터 연결 수 graph = [[0]*(n+1) for _ in range(n+1)] # 컴퓨터 연결관계 그래프 visited = [0]*(n+1) # 연결된 컴퓨터 체크 여부 확인용 리스트 for _ in range(k): a, b = map(int, input().spl..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 접근 방식 - 그래프 접근법 고민하기 (dfs: 재귀함수 활용, bfs: 큐 활용) - 그래프 표현법, 방문 처리 방식 고민 코드 풀이 from collections import deque n, m, v = map(int, input().split()) graph = [[0]*(n+1) for _ in range(n+1)] visited1 = [0]*(n+1)..