BFS 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net (1) 메모리 초과난 코드 (실패) import sys from collections import deque c, r = map(int, sys.stdin.readline().split()) graph = [] visited = [[False] * c for _ in range(r)] start = deque() for i in range(r): l = list(map..

DFS / Union Find 문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 그래프에서 cycle이 존재하면 해당 그래프는 트리가 될 수 없다. 즉, 해당 문제는 어떠한 그래프가 주어졌을 때 cycle이 존재하는지의 여부를 구하고 트리의 갯수를 세는 문제이다. 이 문제는 union find나 dfs를 사용해서 풀 수 있다. 나는 이 문제를 총 2가지 방식으로 풀어보았다. (1) Union Find 이용 사실 이 문제는 ..

백트래킹 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net (1) 처음에 생각한 방식 import sys import heapq n, m = map(int,sys.stdin.readline().split()) graph = [] home = [] chicken = [] for i in range(n): l = list(map(int,sys.stdin.readline().split())) for j in range(n):..

백트래킹 문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M (2) # N과 M (2) (실버 3) import sys n, m = map(int, sys.stdin.readline().split()) result = [0] * m arr = [i + 1 for i in range(n)] checked = [False for _ in range(n)] def dfs(level, begin): if level == m: print(*..

백트래킹 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M (1) # N과 M (1) (실버 3) import sys n, m = map(int, sys.stdin.readline().split()) result = [0] * m arr = [i + 1 for i in range(n)] checked = [False for _ in range(n)] def dfs(level): if level == m: print(*result)..

순열 [1,2,3] 중 2개를 뽑아 순열을 만드는 예시 def dfs(level): if level == r: print(result) return for i in range(len(arr)): if checked[i] == True: continue result[level] = arr[i] checked[i] = True # 중복순열이 안되게 -> 앞자릿수에서 선택한 값은 뒤에서 선택될 수 없음. dfs(level + 1) checked[i] = False # 다시 새로운 result를 만들어낼 때 숫자가 선택될 수 있게 print(level, checked) arr = [i + 1 for i in range(3)] r = 2 result = [0] * r checked = [False] * len(a..