모각코 3회차 - 1/20일, 19시~22시

목표

코드트리 Intermediate Low 과정

Chapter 3. DFS : 깊이 우선 탐색 방법과 그 쓰임에 대해 배우게 됩니다.

 

결과

 

그래프 탐색

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

# Write your code here!
def dfs(graph):
    stack = []
    visited = []
    cnt = 0

    stack.append(1)

    while stack:
        node = stack.pop()
        if node not in visited:
            cnt += 1
            visited.append(node)
            for i in range(len(graph[node])):
                stack.append(graph[node][i])
    
    print(cnt-1)


graph = {}

for e, v in edges:
    if e not in graph:
        graph[e] = [v]
    else:
        graph[e].append(v)

    if v not in graph:
        graph[v] = [e]
    else:
        graph[v].append(e)

if m == 0 or 1 not in graph:
    print(0)
else:
    dfs(graph)

 

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

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

# Write your code here!
def dfs(grid):
    dx = [1, 0]
    dy = [0, 1]

    escapable = 0

    stack = [(0, 0)]

    while stack:
        x, y = stack.pop()

        if x == n - 1 and y == m - 1:
            escapable = 1
            break

        for i in range(2):
            tmp_x = x + dx[i]
            tmp_y = y + dy[i]

            if tmp_x < n and tmp_y < m:
                if grid[tmp_x][tmp_y] == 1:
                    stack.append((tmp_x, tmp_y))
                    grid[tmp_x][tmp_y] = 0

    print(escapable)

dfs(grid)

마을 구분하기

n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]

# Write your code here!
village = []

def dfs(grid, c_x, c_y):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    cnt = 0
    stack = [(c_x, c_y)]
    grid[c_x][c_y] = 0

    while stack:
        x, y = stack.pop()
        cnt += 1
        
        for i in range(4):
            tmp_x = x + dx[i]
            tmp_y = y + dy[i]

            if tmp_x >= 0 and tmp_x < n and tmp_y >= 0 and tmp_y < n:
                if grid[tmp_x][tmp_y] == 1:
                    grid[tmp_x][tmp_y] = 0
                    stack.append((tmp_x, tmp_y))

    village.append(cnt)

for i in range(n):
    for j in range(n):
        if grid[i][j] == 1:
            dfs(grid, i, j)

village.sort()
print(len(village))
for node in village:
    print(node)