6/30 미경이 스터디

Photo by Pietro Mattia on Unsplash

백준 2178 미로탐색

from collections import deque
row, col = map(int, input().split())
map_ =[]
for _ in range(row):
    map_.append(list(map(int, ' '.join(input()).split())))
visited = [[0]*col for _ in range(row)] 
dx = [1, -1 ,0 ,0]
dy = [0, 0, 1, -1]
stack = deque()
stack.append((0,0,1))
visited[0][0] = 1
while stack:
    y,x,dist = stack.popleft()
    visited[y][x] = 1
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0<=nx<col and 0<=ny<row and visited[ny][nx] == 0 and map_[ny][nx] == 1:
            map_[ny][nx] = dist+1
            stack.append((ny,nx,dist+1))
print(map_[row-1][col-1])

내가 이해한 룰

1. 미로의 벽은 0이고 길은 1이다.
2. 각 노드에서 4방향을 순회하며 길이 있는 곳을 찾아서 간다.
3. 주어진 노드 끝까지 닿았을 때의 최소거리를 구하라

문제풀이

1. 처음 접근 했을 때는 dfs가 좀 더 효율적인가? 하는 생각을 했다.
2. 그러나 여러 곳을 방문하다 돌아와야하는 dfs보다 방문한 곳에 1을 더하기만 하면 되는 bfs가 더 효율적이라는 생각이 들었다.(아닐수도 있음)
3. 그래서 스택을 활용하여 시작점 노드를 스택에 넣어주고
4. 들어간 값을 토대로 4방향을 검사하여 방문처리해주고 만약 방문하지 않았고 주어진 다음 지점이 길이라면 (값이 1)
5. 다음지점에 1을 더해주고 스택에 다음지점의 좌표와 거리를 넣어준다.

백준 1260 DFS와 BFS

n, m, start = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    from_, to_= map(int, input().split())
    graph[from_].append(to_)
    graph[to_].append(from_)
def dfs(graph, start, visited=[]):
    visited.append(start)
    for node in sorted(graph[start]):
        if node not in visited:
            dfs(graph, node, visited)
    return visited

def bfs(graph, start):
    stack = []
    visited = [start]
    stack.append(start)
    while stack:
        node_now = stack.pop(0)
        for node in sorted(graph[node_now]):
            if node not in visited:
                visited.append(node)
                stack.append(node)
    return visited
print(*dfs(graph, start,[]))
print(*bfs(graph,start))

내가 이해한 룰

1. 주어진 값들을 받아와서 graph를 초기화해준다.
2. 각각 dfs bfs 방식으로 프린트해준다.
3. (놓친 부분) 노드를 순회할 때 작은 순서대로 순회한다.
4. (놓친 부분2) 공백으로 나뉘어진 값을 반환해야한다.

문제풀이

1. 기본적인 dfs와 bfs를 구현할 수 있느냐를 묻는 문제
2. 양 방향 노드를 graph에 연결하여 선언해준다.
3. dfs는 recursion을 활용하여 노드를 검사해주었다.
4. 빈 리스트를 visited의 디폴트 값으로 받아주고
5. 리스트에 방문한 노드값을 추가해주면서
6. visited에 없는 값이라면 dfs recursion 함수에 넣어 실행시켜준다.
7. bfs는 스택을 만들어 처리했다.
8. dfs처럼 노드들을 파고들어가지 않고 그래프 안의 노드들을 순회하고
9. 마찬가지로 visited에 들어가지 않은 값들만 처리하여준다.