99클럽 코테스터디 4일차 TIL - 백준 1260, 백준 2468

1. 문제: https://www.acmicpc.net/problem/1260

그래프 탐색에 대한 복습 겸 DFS와 BFS 관련 문제를 풀이해보았다.

 

✅ 인접행렬 활용 풀이

import sys
from collections import deque

input = sys.stdin.readline
n, m, v = map(int, input().split())  # 정점의 갯수, 간선의 갯수, 시작지점
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)

for i in range(m):
  start, end = map(int, input().split())
  graph[start][end] = 1  # 양방향 연결
  graph[end][start] = 1

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

  for i in range(n+1):
    if graph[v][i] == 1 and not visited[i]:   # graph[v][i] == 1: v와 i가 연결되어있음
      dfs(i)

def bfs(v):
  q = deque([v])
  visited[v] = True

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

    for i in range(n+1):
      if graph[v][i] == 1 and not visited[i]:
        q.append(i)
        visited[i] = True

dfs(v)
print()
visited = [False] * (n+1)
bfs(v)

 

✅ 인접리스트 활용 풀이

import sys
from collections import deque

input = sys.stdin.readline
n, m, v = map(int, input().split())  # 정점의 갯수, 간선의 갯수, 시작지점
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

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

for i in range(n+1):
  graph[i].sort()
  
"""
인접행렬 때와는 달리 인덱스 순서 없이 연결 노드가 저장되므로, 
여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다 라는 조건에 의해 각 연결된 노드들 정렬
"""

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

  for c in graph[v]:
    if not visited[c]:
      dfs(c)

def bfs(v):
  q = deque([v])
  visited[v] = True

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

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

dfs(v)
print()
visited = [False] * (n+1)
bfs(v)

 

2. 문제: https://www.acmicpc.net/problem/2468

import sys
from collections import deque

sys.setrecursionlimit(10**8)

input = sys.stdin.readline
n = int(input())   # 행, 열
graph = []

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

for i in range(n):
  arr = list(map(int, input().split()))
  maxHeight = max(max(arr), maxHeight)  # 높이의 최대값을 구해 0부터 최대값까지 각 경우의 물에 잠기지 않는 지역 개수를 구하기 위함
  graph.append(arr)

def dfs(x, y, height):
  visited[x][y] = True   # 방문처리
  
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if 0<=nx<n and 0<=ny<n and not visited[nx][ny] and graph[nx][ny] > height:
      dfs(nx, ny, height)

answer = 0

for height in range(0, maxHeight+1):
  visited = [[False] * (n+1) for _ in range(n+1)]
  count = 0
  
  for j in range(n):
    for k in range(n):
      if graph[j][k] > height and not visited[j][k]:
        count += 1   # 영역의 갯수
        dfs(j, k, i)
  answer = max(answer, count)

print(answer)

 

오늘의 배운점

- "최단" 거리를 찾아야하는 경우에는 BFS, 그 외의 경우에는 DFS가 효율이 더 높다.

- print(_, sep="", end="\n")

sep: 출력할 때 어떤 구분자를 넣어서 출력할 것인지? (기본값 빈문자열),

end: 출력할 때 어떤 형식으로 마칠것인지? (기본값 개행문자)

- 공백으로 구분된 숫자들을 정수 배열로 변환 => list(map(int, input().split())