시작이 반

배추흰 지렁이가 인접한(상, 하, 좌, 우) 배추를 보호 한다고 한다. 즉, 이 문제는 배추의 영역을 구하는 문제이다. DFS, BFS둘다 사용 할 수 있지만 DFS의 경우 재귀의 횟수에 따라 메모리, 시간초과가 뜰 수 있다. 이때 sys.setrecursionlimit(n) 을 사용하여 제귀횟수를 제한할 수 있지만 BFS를 사용하는 것이 좋아보인다. 여기서 노드는 배열의 좌표라고 생각한다. DFS 시작 노드에서 인접한 노드 선택하여 방문처리를 하고 탐색을 들어간다. 더이상 탐색할 노드가 없으면 이전노드에 연결되어 있는 점들 중 방문하지 않고 다음으로 큰 노드을 탐색한다. BFS BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내..

처음에 DFS로 풀었지만 메모리 초과가 나왔다. 재귀에 이상이 있음을 확인하였다. 입력크기가 n(1 ≤ n ≤ 500), m(1 ≤ m ≤ 500) 이기 떄문에 재귀로 풀면 메모리 초과가 뜬다. 때문에 BFS를 사용하여 풀었다. BFS (2차원배열 인접 리스트 확인 (상, 하, 좌, 우)) dx, dy를 이용하여 상, 하, 좌, 우 확인 for 문을 이용하여 2차원 배열의 모든 좌표 확인 1. 방문하지 않고, 배열의 값이 1일 경우 큐에 삽입하고 방문 처리를한다. 2. 큐에서 해당 좌표를 꺼내 그 좌표의 상, 하, 좌, 우를 확인한다. 상, 하, 좌, 우에 1이 있고 방문하지 않았다면 큐에 삽입후 방문처리를한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. (큐가 빌때까지) from c..

먼저 2차원 배열을 생성할 수 있어야한다. graph = [list(map(int, input())) for _ in range(n)] 입력을 받으면서 그래프를 만든다. 그래프의 1의 묶음을 찾는 문제이다. 묶음을 찾는 문제들은 DFS로 구현이 가능하다. 처음 구현 코드 DFS익숙하지 않아서 이전에 풀었던 DFS틀에 맞춰서 풀지 못하였다. n = int(input()) graph = [list(map(int, input())) for _ in range(n)] def dfs(x, y, house_count): if x = n or y = n: return False if graph[x][y] == 1: graph[x][y] = house_count dfs(x - 1, y, house_count) dfs(..

DFS, BFS 중 하나를 선택하여 해결할 수 있다. BFS방식으로 문제를 해결하였다. BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. from collections import deque n = int(input()); #컴퓨터 수 graph = [[] for _ in range(n + 1)] e = int(input()); #연결된 선 수 for i in range(e): a, b = map(int, input().split()) graph[a].append(b) graph[b..

DFS와 BFS의 기초 문제이다. DFS DFS는 스택과 재귀를 이용하여 문제를 풀 수 있다. 재귀를 이용하여 문제를 풀었다. 시작 노드에서 인접한 노드 중 숫자가 작은 노드를 선택하여 방문처리를 하고 탐색을 들어간다. 더이상 탐색할 점이 없으면 이전노드에 연결되어 있는 점들 중 방문하지 않고 다음으로 큰 노드을 탐색한다. BFS BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. from collections import deque n, m, v = map(int, input().s..