[이코테] dfs & bfs 문제풀이

 

 

 

 

 

 

graph =  []
n, m = map(int, "4 5".split())

example = [
  "00110",
  "00011",
  "11111",
  "00000"
]

for i in example:
  graph.append(list(map(int, str(i))))

def dfs(i, j):
  if i <= -1 or i >= n or j <= -1 or j >= m:
    return False
  if graph[i][j] == 0:
    graph[i][j] = 1
    dfs(i - 1, j)
    dfs(i + 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)
    return True
  return False

result = 0
for i in range(n):
  for j in range(m):
    if dfs(i, j):
      result += 1
print(result)

 

 

 

graph =  []
n, m = map(int, "15 14".split())

example = [
  "00000111100000",
  "11111101111110",
  "11011101101110",
  "11011101100000",
  "11011111111111",
  "11011111111100",
  "11000000011111",
  "01111111111111",
  "00000000011111",
  "01111111111000",
  "00011111111000",
  "00000001111000",
  "11111111110011",
  "11100011111111",
  "11100011111111"
]

for i in example:
  graph.append(list(map(int, str(i))))

def dfs(i, j):
  if i <= -1 or i >= n or j <= -1 or j >= m:
    return False
  if graph[i][j] == 0:
    graph[i][j] = 1
    dfs(i - 1, j)
    dfs(i + 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)
    return True
  return False

result = 0
for i in range(n):
  for j in range(m):
    if dfs(i, j):
      result += 1
print(result)

 

 

 

 

 

 

from collections import deque

def bfs(n, m, graph, x, y):
    queue = deque()
    queue.append((x, y))
    
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[a][b] + 1
                queue.append((nx, ny))
    return graph[n - 1][m - 1]
 
n, m = 5, 6
graph = [
    [1, 0, 1, 0, 1, 0],
    [1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1]
]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
x = 0
y = 0
print(bfs(n, m, graph, x, y))