문제 설명 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 성능 요약 메모리: 31120 KB, 시간: 1592 ms 분류 백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2024년 3월 8일 01:32:29 문제 설명 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 ..
dfs
문제 설명 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 풀이 이 문제는 BFS, DFS 두 방법 다 사용 가능하다 그래서 두 가지 방법으로 풀어보았다! 1. DFS 배추가 심어진 땅의 개수를 구하는 것이기 때문에 가장 먼저 DFS로 푸는 방법을 떠올렸다 재귀를 돌면서 아직 방문하지 않았으면서 값이 1인 부분을 찾고, 재귀가 끝나면 return True를 해준다 반복문으로 dfs 함수를 호출해 true면 result를 증가해준다 import sys ..
문제 설명 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 구역의 개수를 구하는 문제이기 때문에 DFS로 풀었다! 파이썬은 재귀 limit이 있어서 setrecursionlimit으로 최대 재귀 횟수를 설정해주어야 한다. RGB배열을 만들어 하나씩 꺼내가며 R, G, B구역의 개수 더해가면서 적록색약이 아닌 사람이 봤을 때 구역을 구하였고, G를 R로 바꾸어 적록색약인 사람이 보는 구역의 수를 구했다. import sys sy..
대표 문제 유형 경로 탐색 (최단 거리, 시간) 최단 거리 : BFS 경로의 가짓수(경우의 수) : DFS 네트워크 (연결) 조합 (모든 조합 만들기) 구현 방법 DFS : Stack, 재귀함수 BFS : Queue, LinkedList 무방향 그래프 # 각 노드가 연결된 정보를 표현 (2차원 리스트) # 보통 문제에서 1부터 시작하기 때문에 인덱스 0은 비워둠 graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 표현 (1차원 리스트) visited = [False] * 9 DFS (Depth First Search) DFS를 설명할 때는 보통 ‘번호가 낮은 인접 노드부터 방문..
