[알고리즘] DFS/BFS - 1012 11725 1926 2668 1987

DFS - 깊이 우선 탐색, BFS - 너비 우선 탐색

DFS: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘그래프는 노드와 간선으로 표현되며, 두 노드가 간선으로 연결되어 있을 시 인접하는 것 DFS는 주로 스택 자료구조를 이용한다. BFS: 가까운 노드부터 탐색하는 알고리즘, 주로 큐 자료구조 사용

 

 

1012 유기농 배추

 

import sys
sys.setrecursionlimit(10000)
 
t = int(input())
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def dfs(x, y):  # 깊이우선탐색
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
 
    if nx<0 or nx>=m or ny<0 or ny>=n:
      continue
    elif graph[ny][nx] == 1:
      graph[ny][nx] = 0
      dfs(nx, ny) # 1이면 다음 노드 탐색
 
for _ in range(t):
  m, n, k = map(int, input().split())
  graph = [[0 for _ in range(m)] for _ in range(n)]
 
  for _ in range(k):
    x, y = map(int, input().split())
    graph[y][x] = 1
 
  worm = 0
  for i in range(m):
    for j in range(n):
      if graph[j][i] == 1:
        dfs(i, j)
        worm += 1
  print(worm)

 

자꾸 recursionerror가 떠서 코드 어디가 잘못된건가 진짜 열심히 찾았는데

sys.setrecursionlimit(10000) 해주면 해결이 되는거였다..........

 

11725 트리의 부모 찾기

트리 상에서 연결된 두 정점 = 그래프

코드 흐름: 그래프를 먼저 만들고

그래프를 역추적....?

n = int(input())
 
graph = [[0]*(n+1) for _ in range(n+1)]
 
for _ in range(n-1):
  a, b = map(int, input().split())
  graph[a][b] = 1
  graph[b][a] = 1

 

근데 이런 식으로 연결된 정점이 10만개면.. 코드 잘못짜면 무조건 시간초과 뜰거같다.

import sys
sys.setrecursionlimit(1000000)
 
n = int(input())
tree = [[] for _ in range(n+1)]
parent = [-1] * (n+1)
for _ in range(n-1):
  a, b = map(int, input().split())
  tree[a].append(b)
  tree[b].append(a) # 연결된 트리 정보
 
def dfs(n):
  for x in tree[n]: # 트리
    if parent[x] == -1: 
      parent[x] = n
      dfs(x)
 
dfs(1)
 
for i in range(2, n+1):
  print(parent[i])

 

역시 메모리초과다

ㅋ

ㅋ

ㅋ

는 pypy3이라서 초과떴다고하네용

 

1926 그림

이제 보자마자 약간 bfs 감이 오는듯아닌듯 일단 코드를 짜보자.

from collections import deque
 
n, m = map(int, input().split())
 
dx = [0,0,1,-1]
dy = [1,-1,0,0]
 
def bfs(graph, a, b):
  q = deque()
  q.append((a, b))
  graph[a][b] = 0
  num = 1
 
  while q:
    x, y = q.popleft()
 
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue
      elif graph[nx][ny] == 1:
        graph[nx][ny] = 0
        q.append((nx, ny))
        num += 1
 
  return num
 
graph = [[0] * m for _ in range(n)]
for i in range(n):
  graph[i] = list(map(int, input().split()))
 
picture = []
 
for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      picture.append(bfs(graph, i, j))
 
if len(picture) == 0:
  print(len(picture))
  print(0)
else:
  print(len(picture))
  print(max(picture))

 

2668 숫자 고르기

 

1->3->1 5->5

사이클을 찾고 그것들을 출력하는 문제같다.

 

import sys
 
sys.setrecursionlimit(1000000)
 
n = int(input())
 
graph = [[] for _ in range(n)]
 
for i in range(1, n+1):
  tmp = int(input())
  graph[tmp-1].append(i)
 
check = [0 for _ in range(n+1)]
 
result = []
 
def dfs(num, visited):
  visited.append(num)
  check[num] = 1
  for x in graph[num]:
    if x not in visited:
      dfs(x-1, visited.copy())
    else:
      result.extend(visited)
 
blank = []
for i in range(n):
  if not check[i]:
    dfs(i, blank) 
 
print(len(result))
 
result.sort()
for x in result:
  print(x)

 

어찌어찌 짜봤는데 메모리 초과가 떴다.

메모리를 최대한 아끼기 위해서 defaultdict(?)를 사용해봤따

import sys
from collections import defaultdict
 
sys.setrecursionlimit(1000000)
 
n = int(input())
 
graph = defaultdict(list)
 
for i in range(1, n+1):
  tmp = int(input())
  graph[tmp].append(i)
 
check = [0 for _ in range(n+1)]
 
result = []
 
def dfs(num, visited):
  visited.add(num)
  check[num] = 1
  for x in graph[num]:
    if x not in visited:
      dfs(x, visited.copy())
    else:
      result.extend(visited)
 
for i in range(1, n+1):
  if not check[i]:
    dfs(i, set([])) 
 
print(len(result))
 
result.sort()
for x in result:
  print(x)

 

1987 알파벳

일단 not visited 를 넣어줘야 할거같은 내용이다 방문하지 않은 알파벳이면 이동하고, 아니면 이동을 안해야됨

dfs 쓰는 문제같

 

r, c = map(int, input().split())
board = []
anstmp = 0
for _ in range(r):
  board.append(list(input()))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
 
def dfs(x, y, visited, maxlen):
  global anstmp
  anstmp = max(anstmp, maxlen)
  apb = board[x][y]
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
 
    if 0 <= nx < r and 0 <= ny < c: 
      if apb not in visited:
        visited.add(apb)
        dfs(nx, ny, visited, maxlen + 1)
        visited.remove(apb)
 
visited = set([])
 
dfs(0, 0, visited, 0)
 
print(anstmp)

 

시간초과가 떴다.

코드상으론 괜찮았다고 생각했는데 아마 visited에 값을 넣고 빼주고 not in 이런식으로 해서 시간초과가 떴지 않나 하는 생각이 들어서 true false로 수정해봤다. 알파벳도 ord 사용해서 숫자로 바꿔줌

 

r, c = map(int, input().split())
anstmp = 1
visited = [False] * 26
board = [list(map(lambda x: ord(x) - 65, input())) for _ in range(r)]
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
 
def dfs(x, y, maxlen):
  global anstmp
  anstmp = max(anstmp, maxlen)
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
 
    if 0 <= nx < r and 0 <= ny < c: 
      if not visited[board[nx][ny]]:
        visited[board[nx][ny]] = True
        dfs(nx, ny, maxlen + 1)
        visited[board[nx][ny]] = False
 
visited[board[0][0]] = True
dfs(0, 0, anstmp)
 
print(anstmp)