백준 바이러스(BFS, DFS)

 

 

200730 기상 : 9시 2분

 

---

 

문제 설명

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

​

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

 

​

⛏ 첫 번째

예제는 맞았는데 틀림

N=int(input())
M=int(input())
answer=0
mat=[[0]*(N+1) for i in range(N+1)]
que=[1]
for i in range(M):
    a,b=map(int,input().split())
    mat[a][b]=1
    mat[b][a]=1
visited =[[0]*(N+1) for i in range(N+1)]
visited[1][1]=1
while que :
    x=que.pop()
    for i in range(1,N+1):
        if mat[x][i]==1 and visited[x][i]!=1:
            visited[x][i]=1
            que.append(i)

for i in range(N):
  for j in range(N):
    if mat[i][j]==1:
      answer +=1
      break       
print(answer-1)
# index 보다 0 1로 연결되어서 효율성없이 만듦 그리고 틀림..ㅎ

 

 

⛏ 성공 (BFS)

​

N=int(input())
M=int(input())# 입력 받는
answer=0# 정답 변수
mat=[[] for row in range(N +1)] # 2차원 배열 만듦 각 index를 정점이라고 생각하고 연결된 것 리스트로 넣기
que=[1] # 처음 시작 1
for i in range(M): # M(연결된) 
    a,b=map(int,input().split())
    mat[a].append(b)
    mat[b].append(a)
    # 입력받고 각 index에 연결된 것 넣기

visited =[0]*(N+1)# 방문 배열 만들기
visited[1]=1# 첫번째부터 시작이니까 1
while que : # 큐가 없을 때까지 돌려줌
    x=que.pop()# 처음 시작 값 꺼내줌
    for i in mat[x]: # index 에 있는 값 다 꺼내오기(x 에 연결되어 있는 거 다 가져옴)
      if visited[i]!=1: #  방문 안한 경우 들어감
        que.append(i)# 큐에 넣음
        visited[i]=1# 방문했다고 표시함

for i in range(N+1):
  if visited[i]==1:# 1일 경우 방문 했으니까 answer +=1 
    answer +=1      
print(answer-1)# 자기 자신꺼빼고 값 출력 

 

 

⛏ 추가 (DFS)

 

def dfs(N,v,answer,mat) :
  visited[v]=1
  for i in mat[v]:
    if visited[i]!=1:
      answer =dfs(N,i,answer+1,mat) # 재귀 
  return answer

N=int(input()) # 입력
M=int(input())
answer=0 # 정답 
mat=[[] for row in range(N +1)]
que=[1]
for i in range(M):
    a,b=map(int,input().split())
    mat[a].append(b)
    mat[b].append(a)

visited =[0]*(N+1)
print(dfs(N,1,0,mat))

 

 

---

느낀 점

​

오늘 오리고기 먹었다

빅스비랑 시리랑 자꾸 날씨 다르게 알려줘서

4번 정도 비교했는데 다 시리가 맞았음

빅스비 분발해라

BFS DFS 진ㅉㅏ 너무 모르겠어서 외우라는데ㅠ 외웠다고요

근데 ㅠ 모르겠었는데 더 어려운 7문제 인터넷 보고 따라 하고 참고하니까

풀었네 가장 쉬운 2 문제 ㅎ..