99클럽 코테스터디 6일차 TIL - 백준 4963, 백준 1012

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

해당 문제는 그래프 탐색을 이용하여 영역을 세는 문제다. 단 조금 특이한 점은 "대각선"으로 연결되어있는 사각형도 섬의 영역으로 친다는 점이라서 영역으로 봐야하는 범위가 늘어난다.

 

✅ 풀이

import sys
sys.setrecursionlimit(10**6)    #recursion error를 위해 limit 늘리기
input = sys.stdin.readline

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

def dfs(x, y):
  visited[x][y] = True

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

    if 0<=nx<h and 0<=ny<w and not visited[nx][ny] and graph[nx][ny] == 1:
      dfs(nx, ny)

w, h = map(int, input().split())
while w != 0 and h != 0:
  graph = []
  answer = 0
  
  for _ in range(h):
    graph.append(list(map(int, input().split())))
    visited = [[False] * w for _ in range(h)]

  for i in range(h):
    for j in range(w):
      if not visited[i][j] and graph[i][j] == 1:    # 방문하지 않은 섬 줌 탐색 실행 
        dfs(i, j)
        answer += 1    # 깊이 우선 탐색을 수행한 횟수 == 영역의 갯수

  print(answer)

  w, h = map(int, input().split())

 

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

마찬가지로 그래프 탐색을 이용하여 영역의 갯수를 세는 문젠데, 99클럽 클럽장님께서 추천해주신 문제여서 풀어보았다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

def dfs(x, y):
  visited[x][y] = True

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

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

t = int(input())
for _ in range(t):
  m, n, k = map(int, input().split())   # y, x
  graph = [[0] * n for _ in range(m)]
  visited = [[False] * n for _ in range(m)]
  
  for _ in range(k):
    x, y = map(int, input().split())
    graph[x][y] = 1

  count = 0

  for i in range(m):
    for j in range(n):
      if graph[i][j] == 1 and not visited[i][j]:
        dfs(i, j)
        count += 1

  print(count)

 

오늘의 배운점

- 지역적인 범위 내에서 함수 실행시, 인자로 해당 지역 변수를 따로 넘기지 않아도 된다.