[DFS] 기본

그래프에서 노드와 연결된 간선 정보를 알려주었을 경우

방문 여부를 알 수 있는 배열을 같이 사용하여 해결한다.

 

1차원 배열로 graph를 구성하였을 때 구현

def dfs(graph, v, visited):
    visited[v] = True
    print (v, end=' ')
    for i in graph[v]:
    	if not visited[v]:
            dfs(graph, i, visited)

 

2차원 배열로 graph를 구성하였을 때 구현

def dfs(v):
    visited[v] = 1
    print (v, end=' ')
    for i in range(1,N+1):
    	if visited[i] == 0 and graph[v][i] == 1:
        	dfs(i)

 

바둑판과 같이 직사각형 형태의 값들이 주어지는 경우

상하좌우로 이동하는 경우를 고려한다.

x, y의 값이 음수가 되거나 가로/세로의 크기보다 커지는 경우 조건을 넣어 처리한다.

def dfs(x,y):
    if x<=-1 or x>N or y<=-1 or y>M:
    	return False
    
    if graph[x][y]==1:
    	dfs(x,y+1)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x-1,y)

위 함수에 적절한 처리를 해주어 풀어준다.