Python_수업 (8)

오늘 할 일

DFS/BFS 심화

→ 이차원 리스트 형태

---

복습!

1. 스택과 큐, deque 자료구조
   • deque 사용시
     • popleft() 사용
2. 그래프 자료구조의 의미, 용어
   • 점과 선으로 이루어진다.
   • 정점, 간선, 가중치
   • 유향(일방향) 그래프, 무향(양방향) 그래프
3. 그래프 구조화 : 인접 행렬과 인접 리스트
   1. 빈 판 만들기
   2. 간선 정보 입력
4. 그래프 탐색 : BFS(너비우선탐색)와 DFS(깊이우선탐색)

DFS/BFS 심화

1. 스택 또는 재귀 함수를 활용한 DFS 구현
2. 이차원리스트 형태의 그래프(델타탐색)
3. 이차원리스트에서 DFS/BFS
4. 실습문제: 미로, 미로의 거리

• DFS 특
  • 가장 최근에 탐색한 정점을 우선적으로 방문한다. → 스택 또는 재귀를 통한 구현
  • 스택을 통한 구현
    1. 세팅
    2. 흐음…
  • 재귀를 통한 구현
    1. 세팅
    2. 재귀가 모두 종료될 때까지 방문-탐색 반복
    • 함수에 들어왔다는 것 자체가 방문!! → ex. pop(), popleft() → visited.add(정점)
    • 탐색 → 반복문 돌면서 → 인접 리스트에 있는 정점 → 만약 방문 안했으면 바로 방문 → return DFS(다음정점) and 나머지는 시스템 스택에 저장

그래프

• 일반 ex. 바이러스 문제
• 2차원 ex. 스타크래프트 맵 / 격자모양

2차원 리스트 그래프

• 구조화 : 인접행렬 / 인접리스트 → 입력 받아서 그대로 쓰면 된다!
• [문제] 미로
• 세팅/방문: 정점 번호 → 2차원 리스트 좌표(r, c) Q = [(0, 0)] S = [(r, c)] DFS = [(r, c)]
• 탐색 : 인접행렬/인접리스트에서 반복문 돌리기 → 델타탐색

[문제] SWEA_미로

from collections import deque

T = int(input())

dr = [-1, 1, 0, 0] # 상 하 좌 우
dc = [0, 0, -1, 1]

for tc in range(1, T+1):
    N = int(input())

    maze = [list(map(int, input())) for _ in range(N)]

    #DFS(스택)
    stack = deque()
    visited = set()
    ans = 0

    for r in range(N):
        for c in range(N):
            if maze[r][c] == 2:
                stack.append((r, c))
                break
        if stack:       #????????
            break
            
    while stack:
        # 방문
        r, c = stack.pop()
        visited.add((r, c))

        if maze[r][c] == 3: # 지금 있는 곳이 도착지인가?
            ans = 1
            break
        
        # 탐색
        for d in range(4):
            nr, nc = r + dr[d], c + dc[d]

            if 0 <= nr < N and 0 <= nc < N and (nr, nc) not in visited and maze[nr][nc] != 1:   # 범위를 세 개 다 쪼개는 거는 어떻게 되지? 된다고 하면 그 순서도 중요한가?
                stack.append((nr, nc))
    print(f'#{tc} {ans}')

 

 

[문제] SWEA_미로의 거리

from collections import deque

T = int(input())

dr = [-1, 1, 0, 0] # 상 하 좌 우
dc = [0, 0, -1, 1]

for tc in range(1, T+1):
    N = int(input())

    maze = [list(map(int, input())) for _ in range(N)]

    #BFS(큐)
    queue = deque()
    visited = set()
    ans = 0

    for r in range(N):
        for c in range(N):
            if maze[r][c] == 2:
                queue.append((-1, r, c))
                break
        if queue:       #????????
            break
            
    while queue:
        # 방문
        cnt, r, c = queue.popleft()
        visited.add((r, c)) # 좌표만 넣어야한다!! 계속 변하는 cnt는 넣으면 안된다!!!

        if maze[r][c] == 3: # 지금 있는 곳이 도착지인가?
            ans = cnt
            break
        
        # 탐색
        for d in range(4):
            nr, nc = r + dr[d], c + dc[d]
            if 0 <= nr < N and 0 <= nc < N and (nr, nc) not in visited and maze[nr][nc] != 1:   # 범위를 세 개 다 쪼개는 거는 어떻게 되지? 된다고 하면 그 순서도 중요한가?
                queue.append((cnt+1, nr, nc))

    print(f'#{tc} {ans}')