[Python] 탐색 문제 리마인드(그래프, 미로, BFS,DFS )

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

import sys
from collections import deque

def solution(n,edge):
    graph = [[] for _ in range(n+1)]
    visited = [0] * (n+1)
    
    for link in edge:
        a,b = link[0],link[1]
        graph[a].append(b)
        graph[b].append(a)
    q= deque()
    q.append(1)
    visited[1] = 1
    while q:
        v = q.popleft()
        for i in graph[v]:
            if visited[i] == 0:
                q.append(i)
                visited[i] = visited[v] + 1
    
    return visited.count(max(visited))

 

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

import sys
from collections import deque


def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    for node in range(n):
        if visited[node] == False:
            answer += 1
            q = deque()
            q.append(node)
            visited[node] = True
            
            while q:
                v = q.popleft()
                for i in range(n):
                    if visited[i] == False and computers[v][i] == 1:
                        q.append(i)
                        visited[i] = True
    return answer

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    visited = [[0] * m for _ in range(n)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    q= deque()
    q.append([0,0])
    visited[0][0] = 1
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<= nx < n and 0<= ny <m and maps[nx][ny] == 1 and visited[nx][ny] == 0:
                q.append([nx,ny])
                visited[nx][ny] = visited[x][y] + 1
    
    if visited[n-1][m-1] == 0:
        answer = -1
    else:
        answer = visited[n-1][m-1]
    
    return answer

길찾기가 아닌 연결된 단지, 네트워크 수를 묻는다면,

행렬 전체를 찾는 for문 추가(시작점을 for문 2개로 작성)해주고 visited == False 일때 카운드 해주

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    visited = [[0] * m for _ in range(n)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    for i in range(n):
        for j in range(m):
            if visited[i][j] == 0 and maps[i][j] == 1:
                answer += 1
                q= deque()
                q.append([i,j])
                visited[i][j] = 1
                while q:
                    x,y = q.popleft()
                    for k in range(4):
                        nx = dx[k] + x
                        ny = dy[k] + y
                        if 0<= nx < n and 0<= ny <m and maps[nx][ny] == 1 and visited[nx][ny] == 0:
                            q.append([nx,ny])
                            visited[nx][ny] = 1