bright

import sys
sys.setrecursionlimit(10000000)
n, m = map(int,sys.stdin.readline().split())

graph = [ [] for i in range(n+1) ]

for i in range(m):
  start, end = map(int,sys.stdin.readline().split())

  graph[start].append(end)
  graph[end].append(start)

visited = [False] * (n+1) 

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


cnt = 0 

for i in range(1,n+1):
  if not visited[i] :
    cnt += 1 
    dfs( graph, i, visited)

print(cnt)

그냥 아주 기초적인 bfs 풀이와 유사하다. 

프로그래머스의 네트워크 문제와 비슷한 것 같다. 

다만, 런타임 에러가 난다면 입력 할 때 sys를 import한 다음 아래 식을 사용해서 입력 받는다. 

import sys

sys.setrecursionlimit(10000000)

n, m = map(int,sys.stdin.readline().split())

DFS 

def dfs( v, visited_dfs ):
  if not visited_dfs[v-1] :
    visited_dfs[v-1] = True
    print(v, end=' ')
    
    if v in graph.keys():
      for i in graph[v]:
          dfs( i, visited_dfs )

1. 시작 노드를 stack 에 넣고 방문 처리 

2. stack의 최 상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 stack 에 넣고 방문 처리 

   -> 최 상단 노드 중 방문하지 않은 인접 노드가 없으면 최상단 노드 pop 

3. 반복 

BFS 

def bfs( v, visited_bfs ) :
    queue = deque()
    queue.append(v)

    while queue : 
        now = queue.popleft()

        if not visited_bfs[now-1]:
          visited_bfs[now-1] = True
          print(now, end= ' ')

          if now in graph.keys():
            for i in graph[now]:
              queue.append(i)

1. 탐색 시작 노드를 큐에 넣고 방문 처리

2. 큐에서 노드를 꺼내어 해다 노드의 인접 노드 중 방문하지 않은 모든 노드를 큐에 삽입 하고 방문 처리

3. 반복 

실행 코드 

from collections import deque 

n, m, v = map(int,input().split()) # 노드, 간선, 시작점 

graph = dict()

for i in range(m):
    start, end = map(int,input().split())

    if start in graph:
        graph[start].append(end)
    else:
        graph[start] = [end] 

    if end in graph:
      graph[end].append(start)
    else:
      graph[end] = [start]

for i in graph.keys():
    graph[i].sort()

visited_dfs = [False] * n
visited_bfs = [False] * n  

dfs(v, visited_dfs)
print()
bfs(v, visited_bfs)

개념만 알면 풀 수 있는 문제일 줄 알았는데 생각보다 오래 걸렸다. 

그래프 만들 때, start-end 와 end-start  모두 넣어 주어야 하는 것에 유의하자. 

www.acmicpc.net/problem/1260

def solution(tickets):

    routes = dict()

    for t1, t2 in tickets:
        if t1 in routes:
            routes[t1].append(t2)
        else:
            routes[t1] = [t2]
    
    for r in routes.keys():
        routes[r].sort(reverse=True)

    st = ['ICN']
    ans = []
    while st:
        top = st[-1]
        if top not in routes or len(routes[top])==0:
            ans.append(st.pop())
            
        else:
            st.append(routes[top].pop())

    ans.reverse()
    return ans

... 아직 dfs-bfs 가 익숙하지 않다.  엄청 어렵다. 

step 1 ) 갈 수 있는 경로를 정의 한 routes 딕셔너리를 만든다. 

step 2 ) 문제에서 가능한 알파벳 순으로 나열하라고 했으므로 정렬한다. 이 때, 역으로 정렬하여 pop 했을 때 

           알파벳 순서가 빠른 곳이 먼저 나오도록 한다. 

step 3 ) 시작점은 'ICN' 이다. 

step 4 ) 문제에서 무조건 다 사용할 수 있다고 했으므로, 다음과 같은 알고리즘을 적용할 수 있다. 

           만약 내가 가려는 곳이 routes 에 존재하지 않는다면 ans 에 넣는다. 마지막에 다른 곳에서 이곳에 도착할 

           것이 분명하다.  존재한다면 다음 목적지로 삼으면 된다. 

Reference 

아래 블로그를 참고했음. 설명이 잘 되어있다. 

https://gurumee92.tistory.com/165

from collections import deque

def solution(begin, target, words):

    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

        next_words = []

        for i in words:
            diff = 0 
            for j in range(len(begin)) :
                if i[j] != current[j]:
                    diff += 1 
            
            if diff == 1 : 
                next_words.append(i)

        for next_word in next_words:
            if next_word not in dist:
                dist[next_word] = dist[current] + 1
                queue.append(next_word)

    return dist.get(target, 0)

1. 분류 : BFS 

2. 풀이 방법 

step 1) bfs 알고리즘을 구현하기 위하여 deque 를 사용한다. 

step 2 ) dist = { 단어 : 변환한 수 } 를 표현하는 딕셔너리 이다.  처음에 begin 을 넣고 deque 에도 begin 을 넣는다. 

step 3 ) current 는 지금 검증할 단어이다. 

           -> 만약 current 와 알파벳 1개 차이가 나는 단어가 있다면 next_words 배열에 넣는다.

step 4 ) next_words 가 전에 바뀌었던 단어가 아니라면, dist 와 queue 에 넣어 준다. 

=> 4 단계 까지 오게 되면 모든 단어 변환을 거친다. 

step 5 ) 만약 dist 에 target 이 있다면 ( 변환 가능함을 의미 ) 변환 한 수를 출력하고, 없다면 0 ( default ) 를 출력한다. 

+ tip )  딕셔너리의 get method 

딕셔너리.get( key[ , defualt 값 ] ) 

: 딕셔너리에 key 가 있으면 해당 key의 value를 반환하고, 없으면 default에 지정한 값을 반환한다. 

default 생략 시, 아무런 값도 ( None ) 반환하지 않는다. 

def solution(numbers, target):
    data = [0]
    for i in numbers:
        tmp = []
        for j in data : 
            tmp.append(j+i)
            tmp.append(j-i)
        data = tmp
    return data.count(target)

numbers 안의 값은 더해지거나 빼지거나 2가지 경우의 수를 갖는다. 

모든 numbers 에 대하여 각 경우의 수를 더해 나가면 모든 경우의 수를 가질 수 있다. 

programmers.co.kr/learn/courses/30/lessons/43165

from collections import deque

n, m = map(int,input().split())
graph = []
for i in range(n) :
  graph.append(list(map(int,input())))

# 상 하 좌 우  x 가 세로 y 가 가로 
dx = [ -1, 1 , 0 , 0 ]
dy = [  0, 0, -1,  1 ] 

def bfs( x, y ) : 
  queue = deque()
  queue.append((x,y))

  while queue:
    x, y = queue.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or ny < 0 or nx >= n or ny >= m : 
        continue 
      
      if graph[nx][ny] == 0 : 
        continue 
      
      if graph[nx][ny] == 1 : 
        graph[nx][ny] = graph[x][y] +1 
        queue.append((nx,ny))
  
  return graph[n-1][m-1]

print( bfs(0,0) )

1. 해결 : 그래프의 최단거리를 찾는 문제는 보통 bfs 를 사용해서 푼다. 

2. point : 

- bfs 를 사용할 것이므로 큐를 이용해서 구현한다. 효율성을 위해 deque 를 선언하고 사용했다. 

- 차례대로 큐에 집어 넣고 그 와 가까운 노드들을 방문하여 처리한다는 느낌으로 이해한다. 

www.acmicpc.net/problem/2178

n = int(input()) # 컴퓨터의 수 
m = int(input()) # 연결된 컴퓨터 쌍의 수 

graph = [ [] for _ in range(n+1) ]      # 컴퓨터 연결 관계를 나타낸 그래프 

for i in range(m):
  a, b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

visited = [ False ] * ( n+1 )

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

dfs(graph,1,visited)

cnt = -1
for i in range(n+1):
  if visited[i] == True :
    cnt += 1 

print(cnt)

방법 :  BFS 를 이용해서 풀이. 

유의 :  graph 를 채우는 과정에서, graph[b].append(a) 를 안했더니 틀렸다는 결과를 받았음.

www.acmicpc.net/problem/2606

=> 좀 더 간결한 풀이

n = int(input()) # 컴퓨터의 수 
k = int(input()) # 쌍의 수 

graph=[ [] for _ in range(n+1) ]
for i in range(k):
  s, e = map(int,input().split())
  graph[s].append(e)
  graph[e].append(s)

visited = [False]*(n+1)

def dfs( graph, v, visited):

  if visited[v] :
    return False 
  
  visited[v]= True 
  
  for i in graph[v]:
    dfs( graph,i,visited)
  return True 

dfs(graph,1,visited)

print(visited.count(True)-1)

- idea..

1. 내가 지금 있는 위치에서 1 로 표시된 곳을 찾아 이동해야 한다. 

2. BFS 

from collections import deque 

n,m = map(int,input().split())

graph=[]
for i in range(n):
  graph.append(list(map(int,input())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]


def bfs(x,y):

  queue = deque()
  queue.append((x,y))

  while queue:
    x,y = queue.popleft()

    for i in range(4):
      nx = x+dx[i]
      ny = y+dy[i]

      if nx< 0 or nx>=n or ny<0 or ny>=m :
        continue 
      if graph[nx][ny] == 0 : 
        continue 
      if graph[nx][ny] == 1 :
        graph[nx][ny] = graph[x][y]+1 
        queue.append((nx,ny))

  return graph[n-1][m-1]


print(bfs(0,0))

1. DFS  : 깊이 우선 탐색 , 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.  시간복잡도는 O(N) 

- 인접 행렬 방식  ( 잘 사용 안 함 ) 

: 연결된 것들을 단순지 2차원 배열로 표현한다.  찾는 속도가 빠르지만 크기가 커지면 메모리를 많이 차지함. 

graph = [[] for _ in range(3)]

graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))

graph[2].append((0,5))

print(graph)

결과 : [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]] 

- 인접 리스트 방식  ( 주로 사용 ) 

나와 연결된 것들을 나열한 리스트로 표현한다. 찾는 속도가 늘지만 메모리 효율성이 높다. ( 필요한 정보만 저장하기 때문에 ) 

다음과 같이 재귀함수를 사용하여 구현 가능하다. 

def dfs( graph, v, visited ):

  visited[v] = True 
  print(v, end=' ')

  for i in graph[v]:       # 나랑 연결된 것 중에서 
    if not visited[i]:     # 방문하지 않은 곳이 있다면 
      dfs(graph,i,visited) # 방문한다. 


graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

visited = [False]*9 

dfs(graph,1,visited)

결과 : 1 2 7 6 8 3 4 5 

2. BFS : 너비 우선 탐색 , 가까운 노드 부터 탐색하는 알고리즘. 시간복잡도는 O(N) 

큐 자료구조를 이용하여 구현한다. 

from collections import deque 

def bfs(graph, start, visited ):
  queue = deque([start])
  visited[start] = True 

  while queue:
    v = queue.popleft()
    print(v, end=' ')

    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True 

graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

visited = [False]*9
bfs(graph, 1, visited )

결과 : 1 2 3 8 7 4 5 6