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)

# deque 이용해서 풀었는데 런타임 에러 남.. 

from collections import deque

def contact(spread): 

  while len(spread) > 0 : 

    if spread[0] == '0' :
      if spread[1] == '1' :
        spread.popleft()
        spread.popleft()
        
      else :
        print("NO") 
        return False 

    else :               # 1로 시작하는 경우 
      spread.popleft()   # 먼저 1 뺌 

      if len(spread) < 3 :  # 최소 1001 
        print("NO") 
        return False
      
      for i in range(2):   # 0 2개 빼기 
        if spread.popleft() != '0':
          print("NO") 
          return False

      # 여기 부터는 000~111 무조건 1로 끝나면 됨. 
      while len(spread) > 0 : 
        tmp = spread[0]

        if tmp == '1' : 
          if len(spread) == 1 or spread[1] == '0' : 
            spread.popleft()
            break  

        spread.popleft()    
      
      if tmp != '1' : 
        print("NO") 
        return False

  print("YES") 
  return True 

t = int(input())

data = []
for i in range(t):
  data.append( deque(input()) )

for i in range(t):
  contact(data[i])

# 정규 표현식으로 풀면 된다고 한다... 

-> 정규 표현식 공부하고 다시 도전! 

def fly():
    start, end = map(int,input().split())
    distance = end - start 

    cnt = 0 
    move = 1 
    max_move = 0 

    while max_move < distance : 
      cnt += 1 
      max_move += move 

      if cnt %2 ==0 : 
        move += 1 

    return cnt 


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

for i in range(t):
  data.append(fly())

for i in data:
  print (i)

※ 규칙 찾기 

1. 이동 횟수는 1, 1, 2, 2, 3, 3, .. 이런식으로 반복되어 나온다. 

2. 각 이동 횟수 별 가장 큰 값은, 다음과 같은 방식으로 구할 수 있다. 

    1 -> 1 

    2 -> 1 + 1 

    3 -> 1 + 1 + 2 

    4 -> 1 + 1 + 2 + 2 

    5 -> 1 + 1 + 2 + 2 + 3 

※ 코드 설명 

나의 이동 거리가 전 이동 횟수의 가장 큰 값보다 크고,  현재 이동 횟수 별 가장 큰 값보다 작으면, 현재 이동 횟수의 값을 가짐을 이용. 

현재 이동 횟수의 가장 큰 값은, 숫자를 2번 씩 더해가므로 [ cnt % 2 == 0 ] 인 경우 마다 move 값을 1 씩 올려 주었다. 

www.acmicpc.net/problem/1011

다음 2주간 목표( ~ 10/14 ) : silver 1 으로 올라가기.. 

solved.ac/problems/level/1

# 3003: 킹, 퀸, 룩, 비숍, 나이트, 폰

n = list(map(int,input().split()))
base = [1,1,2,2,2,8]

for i in range(len(n)): 
  print( base[i]-n[i], end=' ')

# 3046: R2

r1,s = map(int,input().split())
r2 = 2*s - r1 

print(r2)

# 5337: 웰컴

print(".  .   .") 
print("|  | _ | _. _ ._ _  _") 
print("|/\|(/.|(_.(_)[ | )(/.")

# 5338: 마이크로소프트 로고

print("       _.-;;-._")
print("'-..-'|   ||   |")
print("'-..-'|_.-;;-._|")
print("'-..-'|   ||   |")
print("'-..-'|_.-''-._|")

# 1000: A+B

a,b = map(int,input().split())

print(a+b)

# 1001: A-B

a,b = map(int,input().split())

print(a-b)

# 1271: 엄청난 부자2 

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

print(n//m)
print(n%m)

# 1550: 16진수 

print(int(input(),16))

# 2338: 긴자리 계산

a = int(input())
b = int(input())

print(a+b)
print(a-b)
print(a*b)

# 2475: 검증수 

n = list(map(int,input().split()))
sum = 0 
for i in n:
  sum += i*i

print(sum%10)

# 2557: Hello world! 

print("Hello World!")

# 2558: A+B -2

a = int(input())
b = int(input())

print(a+b)

# 2845: 파티가 끝나고 난 뒤

l,p = map(int,input().split())
data = list(map(int,input().split()))

for i in data:
  print( i - l*p, end=' ')

# 2914: 저작권

a, i = map(int,input().split())

print( a*(i-1)+1 )

n = int(input()) # 회의의 수 

data=[]
for i in range(n):
  data.append(list(map(int,input().split())))   # [ 시작시간, 끝나는 시간 ]

data=sorted(data, key = lambda x: (x[1],x[0]) )

cnt= 0
m = 0

for meet in data:
  if meet[0] >= m : 
    cnt += 1 
    m = meet[1]

print(cnt)

step1) 가장 빨리 끝나는 순서로 정렬한 수, 시작 시간 별로 정렬한다. 

step2) 제일 처음으로 , 가장 빨리 끝나는 강의가 포함된다. 

step3) 그 이후로는, 앞의 강의가 끝나는 시간에 가장 가깝게 시작되는 강의를 배치하고 그 강의 끝에 다시 가장 가까운 강의를 배치한다. 

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