2025.04.03

TIL(TODAY I LEARN)

---

• WEEK03 :
  그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬

• 3주차 시험을 쳤다. 다행이 다 풀 수 있었다.

---

1338 - 바닥 장식 - 실버4

문제 링크 - https://www.acmicpc.net/problem/1388

내 코드

  import sys
  sys.setrecursionlimit(10**6)
  input = sys.stdin.readline
  
  N,M = map(int,input().split())
  
  graph = []
  graph.append(["0" for _ in range(M+1)])
  for i in range(N):
      x = list(input().strip())
      graph.append(['0'] + x)
  
  visited = [[False for _ in range(M+1)]for _ in range(N+1)]
  
  dy = [0,0,-1,1]
  dx = [-1,1,0,0]
  
  cnt = 0
  def dfs(startx,starty,prev):
      visited[startx][starty] = True
      
      if graph[startx][starty] == "-":
          for i in range(2,4): # -일 땐 좌우로만
              nx = startx + dx[i]
              ny = starty + dy[i]
              if 0< nx <= N and 0< ny <= M and not visited[nx][ny] and graph[nx][ny] == prev:
                  dfs(nx,ny,prev)
  
      
      elif graph[startx][starty] == "|":
          for i in range(0,2): # | 일땐 상하로만
              nx = startx + dx[i]
              ny = starty + dy[i]
              if 0< nx <= N and 0< ny <= M and not visited[nx][ny] and graph[nx][ny] == prev:
                  dfs(nx,ny,prev)
  
      
  for i in range(1,N+1):
      for j in range(1,M+1):
          if not visited[i][j]:
              dfs(i,j,graph[i][j])
              cnt += 1
  print(cnt)

• 첫번째 문제지만 시간이 좀 오래걸렸다. dx,dy를 반대로 적용하고 있었다. dx,dy를 그래프의 행렬인데 x,y축으로 생각해버려 답이 올바르게 나오지 않았다. 다른 문제를 먼저 풀고 다시 보니 다행이 찾아낼 수 있었다.

  문제 분류

• 구현
• 그래프 이론
• 그래프 탐색

---

2667 - 단지번호붙이기 - 실버1

문제 링크 - https://www.acmicpc.net/problem/2667

내 코드

 import sys
 
 input = sys.stdin.readline
 
 N = int(input().strip())
 
 map = []
 
 for i in range(N):
     x = list(input().strip())
     map.append(x)
     
 
 visited = [[False for _ in range(N)] for _ in range(N)]
 
 dx = [0,0,-1,1]
 dy = [-1,1,0,0]
 def dfs(startx,starty,num,house_cnt):
     visited[startx][starty] = True
     for i in range(4):
         nx = startx + dx[i]
         ny = starty + dy[i]
         if 0<= nx < N and 0<= ny < N and visited[nx][ny] == False and map[nx][ny] == num:
            house_cnt = dfs(nx,ny,num,house_cnt) +1
     
     return house_cnt
        
     
 cnt = 0
 result = [] # 집개수 넣을 배열
 for i in range(N):
     for j in range(N):
         if visited[i][j] == False and map[i][j] != '0':
             h = dfs(i,j,map[i][j],1)
             result.append(h)
             cnt += 1
             
 print(cnt)
 result.sort() 
 for i in range(len(result)):
     print(result[i])

문제 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

18405 - 경쟁적 전염 - 골드5

문제 링크 - https://www.acmicpc.net/problem/18405

내 코드

 import sys
 from collections import deque
 input = sys.stdin.readline
 
 N,K = map(int,input().split())
 
 graph = []
 graph.append([0 for _ in range(N+1)])
 for _ in range(N):
     x = list(map(int,input().split()))
     graph.append([0] + x)
     
 S,X,Y = map(int,input().split())
 
 dx = [0,0,-1,1]
 dy = [-1,1,0,0] 
 
 visited = [[0 for _ in range(N+1)]for _ in range(N+1)]
 
 q = deque()
 for k in range(1,K+1):
     for i in range(1,N+1):
         for j in range(1,N+1):
             if graph[i][j] == k:
                 q.append((i,j,k)) #시작 위치 찍어주기
                 visited[i][j] = k 
 
 cnt = 0
 while q:
     if cnt == S: # S초면 그만
         break
     for _ in range(len(q)): # q에 들어간만큼 반복
         x,y,v = q.popleft()
         for i in range(4):
             nx = x + dx[i]
             ny = y + dy[i]
             if  0< nx <= N and 0< ny <= N and visited[nx][ny] == 0:
                 visited[nx][ny] = v
                 q.append((nx,ny,v))
     cnt += 1
 
 print(visited[X][Y])
 

문제 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

• bfs,dfs의 전형적인 문제들이 나왔다고 생각한다.
• 다음 주부터 그리디,dp하는데 화이팅 해보자.