[ 이것이 코딩테스트다 ] 16일차

✏️ 서론

이번시간에는 저번시간에 배운 dfs, bfs알고리즘 문제를 풀어봤다.

---

✏️ 본론

📍 [ 문제 1 ] 음료수 얼려먹기

문제: N x M크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어있는 것으로 간주한다. 이때, 얼음 틀의 모양이 주어졌을 때, 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

dfs로 해결 할 수 있는데,

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문 할 수 있다.
3. 1 ~ 2 번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

n, m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(map(int, input())))

def dfs(x, y):
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    if graph[x][y] == 0:
        graph[x][y] == 1
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

result = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result = result + 1
print(result)

---

📍 [ 문제 2 ] 미로탈출 & 백준 2178 미로탐색

문제

1. 함수를 선언하는 방식
2. 함수를 선언하지 않는 방식

총 두가지 버전으로 문제를 풀어보았다.
나는 함수를 선언하지 않고 푸는 방식이 조금 더 잘 맞았다.
함수를 선언하지 않은 방식은 deque를 쓰지 않아도 풀 수 있는데,
요약하자면 다음과 같다.

1. matrix: 입력값
2. visited: 입력값과 비교할 데이터 ([0]으로 이루어진 N x M 리스트)
   • visited[0][0]: 처음 방문한 곳 = 1
3. dx, dy: 상하좌우 데이터
4. queue: 가장 첫 시작점

while문 queue의 가장 첫번째 원소대입
이후 for문을 통해 상하좌우 계산을 해준다.
i가 0부터 시작하므로 dy = 1인 상을 먼저 본다.
범위 설정을 통해 입력받은 값을 벗어나지 않게한다.
입력받은 값 중 0은 벽이므로 건너뛴다.
matrix[nx][ny] == 1: 갈 수 있는 곳
visited[nx][ny] == 0: 방문하지 않은 곳을 동시에(and) 만족하면
visited[nx][ny] = visited[x][y] + 1 (초기값은 1로 설정함)
print(visited[n-1][m-1]): 0, 0부터 시작하므로 -1 범위 까지 설정

# 함수를 선언한 방식
from collections import deque

n, m = map(int, input().split())

matrix = []

for i in range(n):
    matrix.append(list(map(int, input())))

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

def bfs(x,y):
    queue = deque()
    queue.append((x,y))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if matrix[nx][ny] == 0:
                continue

            if matrix[nx][ny] == 1:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append((nx, ny))
    return matrix[n-1][m-1]

print(bfs(0, 0))


# 함수를 선언하지 않은 방식
n, m = map(int, input().split())
# 입력받은 배열넣기
matrix = []
for i in range(n):
    matrix.append(list(map(int, input())))

# 방문하지 않은 배열
visited = [[0] * m for _ in range(n)]

# 상하좌우선언
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

queue = []
queue.append((0,0))
visited[0][0] = 1

while queue:
    x, y = queue.pop(0)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if matrix[nx][ny] == 1 and visited[nx][ny] == 0:
            visited[nx][ny] = visited[x][y] + 1
            queue.append([nx, ny])

print(visited[n-1][m-1])

---

✏️ 결론

이렇게 dfs, bfs 문제를 풀어봤다.
문제를 풀었는데 이해가 잘 안된다고 생각이 들면,
다른 사람의 코드를 종종 보는편인데 이해되기 쉽게 코드를 작성한 분들을 보면 저렇게 쉽게 작성할 수도있구나 라고 생각이 들었다.

많이 배우고 내것으로 만들어야겠다.