백준 2606

https://www.acmicpc.net/problem/2606

 

 

 

 

 

DFS 파트에서 문제를 들어가서 다른 방법말고 문제를 바로 DFS 풀었다. 

1번 컴퓨터에 연결되어 있는 컴퓨터를 카운트 하면 된다. 

 

책 이코테에 있는 예제를 그대로 활용하였다. 

 

다음을 탐색하는 코드이다. 

def dfs(graph,v,visited):
  # 현재위치 방문처리
  visited[v] =True
  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)
graph = [[],
        [2,3,8],
        [1,4,5],
        [3,5],
        [3,4],
        [7],
        [2,6,8],
        [1,7]
        ]
# 방문된 정보를 1차원 리스트로 표현
visited = [False]* 9
dfs(graph,1,visited)

 

그래서 이 코드를 이용해서 방문처리 할때마다 카운트만 해주면 해결되는 문제이다. 

 

추가로 해줘야하는게 여기서는 그래프가 인접 노드를 표현하는 방식으로 표현 되어있었다. 

n = int(input())
m = int(input())
graph = [[] for i in range(n+1)]
answer = 0 
visited = [False] * (n+1) 
# 입력값 2차원 list로 담기
for i in range(m):
  a,b = map(int, input().split())
  # a는 b랑 연결되어있음
  # list 의 a자리에 a와 연결되어 있는 수들을 담는다
  graph[a].append(b)
  # b는 a랑 연결되어 있음
  graph[b].append(a)

입력되는 값의 인접노드를 새롭게 만들었다. 

그러면 2차원 리스트에 각 위치마다 연결되어 있는 수들이 담긴다. 

 

전체코드)

 

# 입력을 2차원 배열로 담고 
# 각 노드를 돌면서 방문 횟수를 카운트 한다. 
n = int(input())
m = int(input())
graph = [[] for i in range(n+1)]
answer = 0 
visited = [False] * (n+1) 
# 입력값 2차원 list로 담기
for i in range(m):
  a,b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
print(graph)

def dfs(graph, v, visited):
  visited[v] = True
  global answer 
  answer += 1 
 
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i , visited)
dfs(graph,1,visited)
# 처음 1일때도 카운트를 하므로 빼줌
print(answer-1)