[Python3] 무인도 여행 - BFS / DFS

1. BFS

- 코드

#BFS -> Queue

from collections import deque 
dx=[1,0,-1,0]
dy=[0,1,0,-1] #r,u,l,d -> have to be declared outside of the fuction..
    
def bfs(x,y, r,c, field, visited):

    q = deque([(x,y)]) #deque : bidirectional queue
    visited[x][y] = 1 # argument(x, y) passing
    cost = int(field[x][y]) #get values from maps[x][y].. initialize
    while q:
        cx, cy = q.popleft()

        for i in range(4): 
            nr = cx + dx[i]
            nc = cy + dy[i]

            
            if 0<=nr<r and 0<=nc<c and field[nr][nc] !='X': #The order of conditions in a conditional statement is also important.
                #check visit, add cost, append (nr, nc)
                if not visited[nr][nc]:
                    visited[nr][nc] =1
                    cost += int(field[nr][nc]) 
                    q.append((nr,nc))
    
    return visited, cost

def solution(maps):
    answer = []
    r, c = len(maps), len(maps[0]) #limit
    visited=[[0]*c for _ in range(r)]

    for i in range(r):
        for j in range(c):
            if maps[i][j] !='X' and not visited[i][j] :#visited[i][j]==0:

                visited, an = bfs(i,j, r,c, maps, visited)
                answer.append(an)


    return sorted(answer) if answer else [-1]

- 주의사항

 범위체크, deque, solution 함수 바깥쪽 bfs함수 위치

 

 

2. DFS

-코드

-주의사항

  stack, solution 함수 안에 DFS함수 위치

  python 재귀 깊이 1000으로 제한

  ->맨 위에 아래코드 넣어줘야함

import sys
limit_number = 10000
sys.setrecursionlimit(limit_number)