[Python] Intermediate Low - DFS , BFS

 

 

 

#DFS 탐색

 

 

- 그래프 탐색

https://www.codetree.ai/missions/2/concepts/4/problems/graph-traversal/description

코드트리

import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = 1
    for i in range(len(adjList[v])):
        w = adjList[v][i]
        if not visited[w]:
            dfs(w)

n, m = map(int, input().split())
adjList = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    adjList[x].append(y)
    adjList[y].append(x)

dfs(1)
count = 0
for i in range(2, n+1):
    if visited[i] == 1:
        count += 1
print(count)

 

 

 

 

 

- 두 방향 탈출 가능 여부 판별하기

https://www.codetree.ai/missions/2/concepts/4/problems/determine-escapableness-with-2-ways/description

코드트리

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(x, y):
    visited[x][y] = 1
    dxdy = [(1, 0), (0, 1)]
    for dx, dy in dxdy:
        new_x = x + dx
        new_y = y + dy
        if new_x == n-1 and new_y == m-1:
            visited[new_x][new_y] = 1
            return
        if -1 < new_x < len(maze) and -1 < new_y < len(maze[0]):
            if maze[new_x][new_y] == 1 and not visited[new_x][new_y]:
                dfs(new_x, new_y)                

n, m = map(int, input().split())
maze = [0 for i in range(n)]
visited = [[0 for i in range(m)] for i in range(n)]
for i in range(n):
    maze[i] = list(map(int, input().split()))
dfs(0, 0)

if visited[-1][-1] == 1:
    print(1)
else:
    print(0)

 

 

 

 

---

 

 

 

#BFS 탐색

 

 

 

- 네 방향 탈출 가능 여부 판별하기

https://www.codetree.ai/missions/2/concepts/5/problems/determine-escapableness-with-4-ways/description

코드트리

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x, y):
    q = deque()
    visited[x][y] = 1
    q.append((1, x, y))
    while q:
        ans, x, y = q.popleft()
        if x == n-1 and y == m-1:
            break

        dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dx, dy in dxdy:
            new_x = x + dx
            new_y = y + dy
            if -1 < new_x < len(maze) and -1 < new_y < len(maze[0]):
                if not visited[new_x][new_y] and maze[new_x][new_y] == 1:
                    visited[new_x][new_y] = 1
                    q.append((ans+1, new_x, new_y))

n, m = map(int, input().split())
maze = [[] for i in range(n)]
visited = [[0 for i in range(m)] for i in range(n)]
for i in range(n):
    maze[i] = list(map(int, input().split()))

bfs(0, 0)
if visited[-1][-1] == 1:
    print(1)
else:
    print(0)

 

 

 

 

 

# 가중치가 동일한 그래프에서의 BFS

 

 

 

- 최소 경로로 탈출하기

https://www.codetree.ai/missions/2/concepts/5/problems/escape-with-min-distance/description

코드트리

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x, y):
    global ans
    q = deque()
    visited[x][y] = 1
    q.append((0, x, y))
    while q:
        ans, x, y = q.popleft()
        if x == n-1 and y == m-1:
            break

        dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dx, dy in dxdy:
            new_x = x + dx
            new_y = y + dy
            if -1 < new_x < len(maze) and -1 < new_y < len(maze[0]):
                if not visited[new_x][new_y] and maze[new_x][new_y] == 1:
                    visited[new_x][new_y] = 1
                    q.append((ans+1, new_x, new_y))

n, m = map(int, input().split())
maze = [[] for i in range(n)]
visited = [[0 for i in range(m)] for i in range(n)]
for i in range(n):
    maze[i] = list(map(int, input().split()))

bfs(0, 0)
if visited[-1][-1] == 1:
    print(ans)
else:
    print(-1)