[BOJ] 2178 | 미로 탐색

[rhakdnj]

그래프표현방법

• 컴퓨터에게 내가 이러한 그래프를 그렸다고 알려줄 표현방법으로는 인접행렬과 인접리스트가 있다.

인접행렬

• 인접행렬이란 그래프에서 정점과 간선의 관계를 나타내는 정사각형 행렬을 의미한다. 보통 불리언2차원행렬을 쓴다.
• a[1][3] = 1이라는 뜻은 1로부터 3까지 가는 경로가 있다는 의미를 말하며, a[1][2] = 0이라면 1로부터 2까지 가는 경로가 없다는 것을 의미한다.
• 시간복잡도는 O(V^2), 공간복잡도 또한 O(V^2)입니다.

인접리스트

• 인접 리스트(adjacency list)는 그정점에서 정점을 연결하는 것을 하나의 연결 리스트를 통해 표현하는 것을 의미한다.
• 인접리스트는 시간복잡도는 O(V + E), 공간복잡도 또한 O(V + E)이다.

[rhakdnj]

보통 인접리스트로 할 생각을 하고 문제에서 만약에 인접행렬로 주어졌다면 인접행렬로 푸는 것이 좋다.

[rhakdnj]

깊이 우선탐색은 그래프를 탐색할 때 쓰이는 알고리즘으로써 특정한 노드에서 가장 멀리 있는 노드를 먼저 탐색하는 알고리즘이다.

주어진 맵전체를 탐색하며 한번 방문한 노드는 다시한번 방문하지 않기 때문에 만약 인접리스트로 이루어진 맵이면 O(V + E)이고 인접행렬의 경우 O(V^2)가 된다.

[rhakdnj]

문제 링크

---

📌 TODO

• [x] 풀이
• [x] 정리

[rhakdnj]

돌다리를 두들겨 보고 가는 방법

def dfs(here: int):
    visited[here] = 1; 
    for there in adj[here]:
        if visited[there]: continue
        dfs(there);

일단 호출하고 생각하는 방법

def dfs(here: int):
    if visited[here]: return
    visited[here] = 1; 
    for there in adj[here]:
        dfs(there);

[rhakdnj]

기본 코드 예시

def dfs(y, x):
    global visited, arr, n, m
    print(y, x)
    visited[y][x] = 1
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if ny < 0 or nx < 0 or ny >= n or nx >= m: continue
        if arr[ny][nx] == 1 and not visited[ny][nx]:
            dfs(ny, nx)

def solution():
    global arr, visited, ret, n, m
    for i in range(n):
        arr.append(list(map(int, input().split())))

    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1 and not visited[i][j]:
                ret += 1
                dfs(i, j)
                print('----------------------------------------------------')

    print(ret)

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
n, m = map(int, input().split())
arr = []
visited = [[0] * m for _ in range(n)]
ret = 0
solution()

[rhakdnj]

가중치가 같을 때 최단거리는 BFS를 사용하면 된다!!!!

[rhakdnj]

dq = deque([(y, x)]) dq를 초기화 할 때는 항상 [] 연결리스트안에 tuple을 넣는 것이므로 위와 같은 방식으로 초기화하여야한다.

햇갈릴 때는 deque도 [] 리스트이다.

dq = deque([(y, x)])

dq = deque((y,x))