bright

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

import sys
sys.setrecursionlimit(50000)

def dfs(y,x):

  if x <0 or y<0 or x>=m or y>=n : 
    return False 

  if graph[y][x] == 1 : 
    graph[y][x] = 0  # 방문처리 
      
    dfs(y-1,x)
    dfs(y+1,x)
    dfs(y,x-1)
    dfs(y,x+1)

    return True
  return False 
  
  

t = int(input())
t_cnt = []

for i in range(t):

  m, n, k = map(int,sys.stdin.readline().split()) # 가로 세로 배추 

  graph = [ [0]*m for i in range(n) ]

  for i in range(k):
    a, b = map(int,input().split())
    graph[b][a] = 1 
  
  cnt = 0

  for y in range(n):
    for x in range(m):
      if dfs(y,x) == True:
        cnt += 1

  t_cnt.append(cnt)


for i in t_cnt:
  print(i)

1. 풀이 : dfs 사용 

2. 유의점 :  계속 런타임 에러 나서 한참 헤맸는데 위에  import sys ; sys.setrecursionlimit(50000)   이 코드만 넣으면 바로 해결 된다. 파이썬은 기본이 재귀가 1000 으로 설정되어 있어서 그렇다고 한다. 아마 확인하는 예제 중에 재귀가 1000이 넘어가는 것이 있는 듯 하다.. 

www.acmicpc.net/problem/1012

n = int(input()) # 지도의 크기 
graph = []

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

def dfs(x,y,num):

  if x <0 or y<0 or x>=n or y>=n : 
    return False 
  
  if graph[x][y] == 1 : 

    graph[x][y] = num+1

    dfs(x-1,y,num)
    dfs(x+1,y,num)
    dfs(x,y-1,num)
    dfs(x,y+1,num)

    return True 
  return False 

num = 1 
for x in range(n):
  for y in range(n):
    if dfs(x,y,num) == True:
      num += 1 

cnt_num = [0] * (num+1)

for x in range(n):
  for y in range(n): 
    if graph[x][y] != 0 :
      cnt_num[ graph[x][y] ] += 1 

total_num = cnt_num[2:num+1]
total_num.sort()

cnt  = len(total_num)
print(cnt)
for i in range(cnt):
  print(total_num[i])

참고 ) 음료수 얼려 먹기 문제 bright-code.tistory.com/78?category=423266

1. 풀이 방법 : dfs 이용 

2. 코드 설명 

dfs 를 사용하여 푼다. 

1 이면 집을 의미한다. 문제에서는 단지 번호를 1 부터 붙였지만, dfs 처리가 어려워서 나는 2 부터 붙였다. 

한 번 dfs  함수를 돌 때, 나와 붙어 있는 것들은 모두 num+1 로 바꿔 준다. 

나중에 숫자 별로 집의 수를 세어서 cnt_num 리스트에 넣어 주었고, 

위 코드에서는 0, 1 의 단지에 속한 집이 없으므로 필요한 부분만 넣은 리스트인 total_num 을 선언해 주었다. 

오름차순으로 sort 하고 길이와 값을 출력한다. 

www.acmicpc.net/problem/2667

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)