정글 TIL 14(01.24)

짧은 글쓰기

앞으로 TIL에 짧게라도 글을 쓰려고 한다. 생각하는 힘이 부족하다는 것을 알고는 있었지만 생각하기 위해 노력하지 않았었는데, 결국 겉으로 드러나고 있는 모양이다. 학교를 졸업하고 사회에 나오니 숨겨져있던 나의 때묵은 문제들이 속속들이 나오고 있다.
그래도 다행이다. 아직 정글 초반이라 앞으로 남을 5개월이 짧은 시간이 아니니 의식하고 노력하면 분명 변화가 생기리라 생각한다. 그리고 정글이라는 일 때문에 만난 사이지만 멘토처럼 필요한 조언들을 아낌없이 해주신 백코치님께도 감사하다.

1260 DFS와 BFS

• 개요

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.
정점 번호는 1번부터 N번까지이다.

입력 :
4 5 1
1 2
1 3
1 4
2 4
3 4

출력 :
1 2 4 3
1 2 3 4

• 추상화

• 주어진 정수와 필요한 리스트들을 생각해봅니다.
• DFS 탐색과 BFS 탐색 방법을 쓰기 위해서는 노드간의 간선을 2차원 리스트에 저장해야 합니다.
• 그리고 이미 탐색한 노드를 들르지 않게 체크해줄 visited 리스트를 생성해야합니다.
• dfs는 deque를 이용합니다.

• 구체화

• 주어진 정수 n, m, v를 담을 변수와 노드의 연결을 나타낼 이중리스트인 elist, 방문 여부를 확인할 visited, deque를 담을 que 리스트를 생성합니다. 리스트의 인덱싱을 위해 s,e 변수를 생성합니다.
• 내표 포기법으로 elist를 m + 1(0을 포함한 간선의 갯수)빈 배열로 채워주고, visited의 길이도 n + 1(0을 포함한 노드의 갯수)로 만들어줍니다. 두 노드를 입력받아 s,e로 elist에 순서를 바꿔 저장합니다.
• queue stack에서 pop받아 현재 노드의 위치를 제공받습니다. 지금 노드의 visited가 0이라면 1로 바꿔주고 현재 노드의 elist 요소들을 stack queue에 담아줍니다.
• dfs와 bfs의 차이는 stack에서 pop을 popleft로 받느냐, pop으로 받느냐의 차이뿐이다.

• 구현

from collections import deque
import sys

input = sys.stdin.readline
n, m, v = map(int, input().split())
elist = [[] for _ in range(m + 1)]
stack = deque()
stack.append(v)
visited = [0] * (n + 1)

for i in range(m+1):
    s, e = map(int, input().split())
    elist[s].append(e)
    elist[e].append(s)

while stack:
    now = stack.pop() #
    if visited[now] == 0:
        visited[now] = 1
        print(now, end = " ")
        for x in elist[now][::-1]:
            stack.append(x)

print("")
stack = deque()
stack.append(v)

visited = [0] * (n + 1)

while stack:
    now = stack.popleft()
    if visited[now] == 0:
        visited[now] = 1
        print(now, end = " ")
        for x in elist[now]:
            stack.append(x)

2178 미로 탐색

• 추상화

• 필요한 변수와 리스트들을 예상합니다.
• 입력받는 미로는 이중 리스트로 구현합니다.
• 미로를 탐색하기 위한 방향키를 구현합니다.
• 미로를 벗어날 조건, 벽을 만나는 조건, 이동하는 조건을 구현합니다.

• 구체화

• 입력 정수를 받을 n,m, 미로를 담을 이중 리스트는 빈배열로 선언하여 for 문으로 append합니다. 방향키는 상, 하, 좌, 우로 dx,dy에 리스트로 담습니다. stack queue를 구현하기 위한 que와 현재 위치 x, y, 이동할 위치인 nx, ny는 bfs 함수내에 저장합니다.
• x, y는 que에서 pop받고 방향이 4개 있으니 for문을 4번 돌립니다. maze list의 미래의 인덱스의 요소를 확인해서 진행 여부를 확인하고, 나아갔다면 다음 위치 값에 현재 값+1을 저장해주고, que에 append 해줍니다.

• 구현

from collections import deque

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

for _ in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0] # 위, 아래를 탐색한다.
dy = [0, 0, -1, 1] # 좌, 우를 탐색한다.
queue = deque()
queue.append((x, y))

# 너비 우선 탐색
def bfs(x, y):

    while queue:
        x, y = queue.popleft()  # 현재 x, y 위치를 queue에서 받는다.
    
        # 현재 위치에서 4가지 방향으로 위치 확인
        for i in range(4):
            nx = x + dx[i] # 현재 위치에서 위, 아래를 확인한다.
            ny = y + 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[x][y] + 1
            # 현재 위치의 값에 1을 더해 다음 위치에 1을 더한다.
            queue.append((nx, ny))
            # 다음 위치를 queue에 추가한다.
  
  # 마지막 값에서 카운트 값을 뽑는다.
    return graph[n-1][m-1]

print(bfs(0, 0))