99클럽 코테 스터디 18일차 TIL + DFS/BFS

오늘의 문제 - DFS/BFS

백준 2667 - 단지번호붙이기

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

---

내 풀이 및 접근 방식

DFS 이용 풀이

import sys

n = int(sys.stdin.readline())
nmap = []
for _ in range(n):
    nmap.append(sys.stdin.readline().rstrip())


v = [[False for _ in range(n)] for _ in range(n)]	# 방문 체크
home_num = 0 # 단지수
cnt = 0 #   집 수
home_cnts = [] # 집 수 리스트


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

def dfs(cx, cy):
    global cnt
    v[cx][cy] = True
    cnt += 1
    for i in range(4):
        nx = cx + dx[i]
        ny = cy + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if not v[nx][ny] and nmap[nx][ny] == '1':
                dfs(nx, ny)


for i in range(n):
    for j in range(n):
        if not v[i][j] and nmap[i][j] == '1':
            home_num += 1
            dfs(i, j)
            home_cnts.append(cnt)
            cnt = 0

home_cnts.sort()
print(home_num)
for hc in home_cnts:
    print(hc)

 

각 집을 방문했는지 체크하기 위해 v 리스트를 사용했는데, 세션을 통해 굳이 이런 방문처리가 필요없음을 알았다.
방문한 집들은 nmap을 0으로 바꿈으로써 방문 처리 가능하다. 이렇게 수정할 경우, 조건문도 더 간단해져서 좋은 것 같다.

---

챌린저 문제

이번에 챌린저 문제도 함께 풀어보려고 했으나 나에겐 넘나 어려웠던 문제,, 세션에서 공유해주셨던 풀이 방식이라도 정리하고 넘어가자~

백준 5547 - 일루미네이션

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

 

 

이 문제가 어려웠던 이유는 2가지이다.

1. 입력은 이차원 배열이지만, 육각형의 배열이라는 점에서 이동 방향의 설정
2. 건물 외벽을 어떻게 셀 것인지

첫번째 문제는 기존 동서남북 이동 방향 탐색과 다르게 여섯가지 방향을 모두 탐색하는 것으로 해결 가능하다. 이때 짝수줄, 홀수줄에 있는지에 따라 좌표를 계산한 방향이 바뀌므로 주의해야한다.

두번째 문제는 건물 외벽이 흰색 부분(건물이 없는 부분)과 회색(건물) 사이에 생성되는 사실을 이용하면 된다. 건물이 없는 부분을 차례로 탐색하여 건물이 있는 부분을 만날 때마다 개수를 세면 이는 곧 벽의 개수가 된다.

=> 그런데 이때 문제는 바깥 경계에 있는 외벽들을 세지 못한다는 것이다. 이를 위해, 경계에 흰색 부분을 한줄씩 추가해서 초기 배열을 설정한다.

내 이해를 돕기 위했던 그림들..

흰색 경계 추가 => 행과 열 2씩 늘리기

짝수줄과 홀수줄에 따른 방향 이동 좌표 차이

 

코드는 다른 분 코드 가져오기..

from collections import deque
from sys import stdin
input = stdin.readline

w, h = map(int, input().split())
graph = [[0 for _ in range(w+2)] for _ in range(h+2)] # 외밖과 닿는 면을 다 흰색으로 둘러주기 위해 +2
for i in range(1, h+1):
    graph[i][1:w+1] = map(int, input().split())

dy = [0, 1, 1, 0, -1, -1]
dx = [[1, 0, -1, -1, -1, 0], [1, 1, 0, -1, 0, 1]] # 짝수줄, 홀수줄 범위내 이동거리 설정

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    visited = [[False for _ in range(w+2)] for _ in range(h+2)] # 방문체크 배열 생성
    visited[y][x] = True
    cnt = 0
    while queue:
        y, x = queue.popleft()

        for i in range(6):
            yy = y + dy[i]
            xx = x + dx[y % 2][i]
            if 0 <= yy < h+2 and 0 <= xx < w+2:
                if graph[yy][xx] == 0 and not visited[yy][xx]:
                    queue.append((yy, xx))
                    visited[yy][xx] = True
                elif graph[yy][xx] == 1:
                    cnt += 1
    return cnt

print(bfs(0, 0))

# 출처: https://reliablecho-programming.tistory.com/110

---

회고

미들러 문제의 경우 이전에 풀었던 문제이기도 하고, dfs, bfs 기본적인 알고리즘만 알고 있으면 풀 수 있었던 문제같다.

 

세션에서 dfs 알고리즘에서 global을 쓰는 것과 return을 사용하여 반환값을 재귀적으로 사용하는 것 중 나은 방식은 무엇인지에 관한 내용이 나왔었다. 결론은 코딩테스트에서는 global을 사용하는 것이 더 직관적일 수 있으나 실무에서는 전역 변수를 사용하는 것은 지양되는 것 같다.