[이코테] DFS / BFS

3. 음료수 얼려 먹기

150

내 코드 (BFS)

from collections import deque

n, m = map(int, input().split())
arr = []

for _ in range(n):
    temp = list(map(int, input()))
    arr.append(temp)
    
# 동북서남
move_h = [0, -1, 0, 1]
move_w = [1, 0, -1, 0]
    
def bfs(h, w):
    queue = deque()
    queue.append([h, w])
    
    while queue:
        hh, ww = queue.popleft()
        
        for i in range(4):
            temp_h = hh + move_h[i]
            temp_w = ww + move_w[i]
            
            if ( 0 <= temp_h < n and 0 <= temp_w < m and arr[temp_h][temp_w] == 0):
                arr[temp_h][temp_w] = 1
                queue.append([temp_h, temp_w])
    
cnt = 0
for i in range(n):
    for j in range(m):
        if ( arr[i][j] == 0 ):
            arr[i][j] = 1
            bfs(i, j)
            cnt += 1
            
print(cnt)

내 코드 (DFS)

n, m = map(int, input().split())
arr = []

for _ in range(n):
    temp = list(map(int, input()))
    arr.append(temp)
    
def dfs(h, w):
    if ( h < 0 or h >= n or w < 0 or w >= m ) or arr[h][w] == 1:
        return 0
    arr[h][w] = 1
    
    dfs(h, w+1)
    dfs(h-1, w)
    dfs(h, w-1)
    dfs(h+1, w)
        
    return 1
    
cnt = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == 1:
            cnt += 1
            
print(cnt)

---

4. 미로 탈출

from collections import deque

n, m = map(int, input().split())
arr = []

for _ in range(n):
    temp = list(map(int, input()))
    arr.append(temp)
    
move_h = [1, -1, 0, 0]
move_w = [0, 0, 1, -1]
    
def bfs(h, w):
    queue = deque()
    queue.append([h, w])
    
    while queue:
        hh, ww = queue.popleft()
        
        for i in range(4):
            temp_h = hh + move_h[i]
            temp_w = ww + move_w[i]
            
            # 지도 밖으로 나가면 무시
            if ( temp_h < 0 or temp_h >= n or temp_w < 0 or temp_w >= m ):
                continue
                
            if ( arr[temp_h][temp_w] == 0 ):
                continue
            
            if ( arr[temp_h][temp_w] == 1 ):
                queue.append([temp_h, temp_w])
                arr[temp_h][temp_w] = arr[hh][ww] + 1
    
bfs(0, 0)
print(arr[-1][-1])

로직

• 해당 로드를 처음 방문하는 경우에만 좌표를 재설정 해주는 것이 포인트

---

<15> 특정 거리의 도시 찾기

340 (실버2) 실패 문제

DFS (풀었지만, 메모리 초과)

n, m, k, x = map(int, input().split())
arr = [[0] * (n+1) for _ in range(n+1)]

dis = [100] * (n+1)
dis[x] = 0

for _ in range(m):
    a, b = map(int, input().split())
    arr[a][b] = 1
    
def dfs(h, w):
    dis[w] = min(dis[w], dis[h] + 1)
    
    for i in range(1, n+1):
        if ( arr[h][i] == 1 ):
            dfs(w, i)

for i in range(1, n+1):
    if ( arr[x][i] == 1 ):
        dfs(x, i)
        
check = False
for i in range(len(dis)):
    if dis[i] == k:
        check = True
        print(i)

if ( check == False ):
    print(-1)

정답 (못품)

from collections import deque

n, m, k, x = map(int, input().split())
graph = [ [] for i in range(n+1) ]

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

q = deque([x])

while q:
    now = q.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            q.append(next_node)
            
check = False
for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        check = True
        
if check == False:
    print(-1)

로직

---

<16>