bright

www.acmicpc.net/problem/1697

from collections import deque 

n, k = map(int,input().split())
t = [0]*100001

def bfs():
  q = deque()
  q.append(n)

  while q:
    a = q.popleft()

    if a == k : 
      print( t[k])
      return 
    
    for b in ( a-1, a+1, a*2):
      if 0<= b < 100001 and not t[b]:
        t[b] = t[a] +1
        q.append(b)

bfs()

n부터 시작 -> 이동 가능한 칸으로 이동 -> 그 칸에서 다시 센다 

한 번 처리된 곳은 또 가지 않는다. 

생각해보면 처음 나왔을 때의 값보다 작은 값이 들어오지 않는다. 

+) 이걸 dfs 로 접근하면 무한 loop가 나온다. 

www.acmicpc.net/problem/1743

from collections import deque

n, m , k = map(int,input().split()) # 세로 가로 음식물 수 
graph = [ [0]*m for i in range(n)]
for i in range(k):
  a,b = map(int,input().split())
  graph[a-1][b-1] = 1 


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

def bfs(x,y):
  q = deque()
  q.append((x,y))
  graph[x][y] = 0 
  cnt = 1 

  while q : 
    a, b= q.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]

      if nx<0 or nx>=n or ny<0 or ny>=m : 
        continue 
      if graph[nx][ny] == 1:
        cnt += 1 
        q.append((nx,ny))
        graph[nx][ny] = 0 
  return cnt 

tmp = 0 

for i in range(n):
  for j in range(m):
    if graph[i][j] != 0 :
      tmp = max(tmp, bfs(i,j))

print(tmp)

# 11725

from collections import deque 

n = int(input()) # 노드의 수 

tree = [ [] for _ in range(n+1) ]
for i in range(n-1):
  a, b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)

def bfs():

  q = deque()
  q.append(1)
  visited = [0] * (n+1)
  visited[1] = 1

  while q :
    x = q.popleft()
    for i in tree[x]:

      if visited[i] == False:
        visited[i] = x
        q.append(i)
  
  return visited
    
result = bfs()

for i in range(2,len(result)):
  print(result[i])

visited 리스트에 부모 노드를 저장함. 

1 -> 1과 연결된 것의 부모를 1로 설정하고 방문 처리한 뒤, queue에 넣음 -> 반복.. 

1. 시간 초과 코드 

# 2644

n = int(input()) # 전체 사람의 수 
a, b = map(int,input().split())
m = int(input()) # 관계의 수 

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

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

def bfs(x, y):
  p ,cnt = 0, 1

  while 1: 
    for i in range(1,n+1):
      if x in graph[i]:
        p = i 
        break 
    
    if p == 0 : return -1 
    else : cnt += 1 
    
    if y in graph[p] : return cnt 
    else : x = p  

print( bfs(a,b) ) 

2. 정답 코드 

# 2644
from collections import deque 

n = int(input()) # 전체 사람의 수 
a, b = map(int,input().split())
m = int(input()) # 관계의 수 

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

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


def bfs(s, e):
  cnt = 0 
  queue = deque()
  queue.append(s) 
  visited = [False] * (n+1)  # 한 번 방문했는데 없던 곳 또 가지 않는다. 

  while queue:
    cnt += 1  # 한 단계 건널 때 마다 촌수 추가 
    
    for _ in range(len(queue)): # 지금 queue의 원소 만큼 반복 
      x = queue.popleft()

      if x == e : 
        return cnt-1
      
      for y in graph[x]:
        # 방문 안한 부분이 있으면 queue에 넣고 방문처리 
        if visited[y] == False:
          visited[y] = True 
          queue.append(y)
  
  return -1 

print( bfs(a,b) ) 

import sys
sys.setrecursionlimit(10000000)

m, n, k = map(int, input().split()) # 세로 가로 직사각형 수 

# 직사각형으로 채워지면 1, 안 채워지면 0
graph = [ [0]*n for _ in range(m) ]

for i in range(k):
  s1, e1, s2, e2 = map(int,sys.stdin.readline().split())

  for x in range(s1,s2):
    for y in range(e1, e2):
      graph[y][x] = 1 

def dfs ( x, y, cnt ):
  graph[y][x] = 1 
  cnt += 1 

  move_x = [-1,1,0,0] # 가로 -> n 
  move_y = [0,0,-1,1] # 세로 -> m 

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

    if nx < 0 or ny < 0 or nx >=n or ny>=m : 
      continue 
    if not graph[ny][nx] :
      cnt = dfs(nx,ny,cnt)
  
  return cnt

area = []

for x in range(n):
  for y in range(m):
    if not graph[y][x]:
      cnt = 0 
      area.append(dfs(x,y,cnt))

print( len(area) )
area.sort()
for i in range(len(area)):
  print(area[i], end=' ')

step 1 ) 런타임 에러 방지를 위해 sys import 하고  graph 선언 

           직사각형으로 채워질 부분은 1, 채워지지 않은 부분은 0 으로 설정한다. 

step 2 ) 직사각형의 좌표값을 입력받아 graph 채우기  -> 실제로 출력해보면 거꾸로 나오긴하는데 상관 없음 

step 3 ) dfs 구현, 가로 세로로 움직이면서 연결된 영역 세기 

           각 영역별 넓이를 구해야 하므로 dfs 가 진행 될 때마다 cnt 를 세어주고 return 하는 식으로 계산한다. 

step 4 ) graph 전체를 탐색하면서 dfs 를 진행한다. 이 때 돌려 받은 cnt 의 값을 각 구역의 넓이를 저장하는 area에 저장

step 5 ) area 의 길이와, 정렬한 결과를 출력

import copy
import sys
sys.setrecursionlimit(10000000)

n = int(input())

graph = []
max_h = 0 
for i in range(n):
  graph.append(list(map(int,sys.stdin.readline().split())))
  max_h = max( max_h, max(graph[i]))

save = [0] * ( max_h +1 )
save[0] = 1  # 비가 안오면 전 영역( 1개 ) 이 안전하다.

def dfs ( x,y,h, tmp_graph):

  move_x = [-1,1,0,0] # 가로 
  move_y = [0,0,-1,1] # 세로 

  tmp_graph[x][y] = 0 

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

    if nx <0 or ny <0 or nx>=n or ny>= n : 
      continue 
    if tmp_graph[nx][ny] >= h : 
      dfs ( nx, ny, h, tmp_graph)

for h in range(1, max_h+1):
  tmp = copy.deepcopy(graph)
  cnt = 0 
  for i in range(n):
    for j in range(n):
      if tmp[i][j] >= h : 
        dfs(i,j,h,tmp)
        cnt += 1 
  save[h] = cnt 

print(max(save))

step 1 ) 그냥 입력 받으면 런타임 에러 나니까 import sys 

step 2 ) graph 입력 받기 , 가장 큰 높이 까지만 찾아보면 되니까 가장 큰 높이 구하기 

step 3 ) 각 높이 별 안전한 영역 저장할 list 선언 ( save ) 

           단, 높이가 0 일 때는 모두 다 하나의 안전한 구역이므로 1 로 설정. 

step 4 ) dfs 구현 하기. 가로 세로로 움직이며 다음과 같은 조건 부여

           ① 움직인 결과 그래프 안에 있는지  ② 현재 검사하고 있는 높이보다 높으면 dfs 진행 

            ③ 방문 처리를 위해서 dfs 진행한 구역은 값을 0으로 만들어주기 

step 5 ) 1 ~ 가장 높은 높이까지 반복.  기존 graph 는 바뀌면 안되니까 깊은 copy 를 통해 각 높이 별로 복사해서 사용 

           깊은 복사는 copy module 로 구현 가능하며,  a = copy.deepcopy( b ) 와 같이 쓴다. 

step 6 ) 각 높이 별 안전한 구역의 개수 세어서 저장, 가장 큰 값 출력하기 

import sys
sys.setrecursionlimit(10000000)

def island(w,h):

    graph = []
    for i in range(h):
      graph.append( list(map(int,sys.stdin.readline().split()))) 

    move_x = [ -1, 1, 0, 0, -1,-1,1,1 ]  # x는 세로, 순서대로 가로 세로 대각선 
    move_y = [ 0, 0, -1, 1, -1,1,-1,1 ]  # y는 가로
    
    def dfs ( x,y ) : 
        graph[x][y] = 0

        for i in range(8):
            nx = x + move_x[i]
            ny = y + move_y[i]

            if nx<0 or ny<0 or nx>=h or ny>=w :
              continue

            if graph[nx][ny] : 
              dfs( nx, ny )
              continue

    cnt = 0 

    for y in range(w):
      for x in range(h):
          if graph[x][y]:
            dfs(x,y)
            cnt += 1 
    return cnt 


p = []

while 1: 
    w, h = map(int,sys.stdin.readline().split()) # 지도 너비, 높이 <= 50 
    if w == 0 and h == 0 : 
        break 
    else:
        p.append( island(w,h) )

for i in range(len(p)):
  print(p[i])

거의 구현 문제다.. 

1. 섬과 바다 지도를 graph 에 받아오기 

2. 만약 내가 지금 방문한 노드가 섬이라면, 인접한 섬 방문하는 dfs 재귀 방법 사용 

   ( 인접한 섬을 방문하는 경우의 수는 가로 2개 세로 2개 대각선 4개하여, 총 8가지 이다. ) 

3. 한 번 탐색을 끝나면 섬 하나가 끝난 것이므로 cnt +1 

tip) 런타임 에러 해결 

-> 보토 입력값이 크고 파이썬은 조금 느린 언어다 보니까 입력하는 부분에서 런타임 에러가 발생할 수 있다. 

import sys

sys.setrecursionlimit(10000000)

w, h = map(int,sys.stdin.readline().split())

위의 코드를 통하여 해결한다. ( 모든 입력 부분에 sys.stdin.readline() 을 사용한다 )

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