브루트포스 : 이제 좀 깊이가 생기는

#14500번 테트로미노 https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

일단 몇 가지 개념을 짚고 넘어가자. 

먼저 지금 계속 하고있는

브루트포스 (brute force) : 완전탐색 알고리즘. 가능한 모든 경우의 수를 탐색하면서 요구조건에 맞는 결과를 가져옴

 

그리고 이와 비슷한 개념인

백트래킹(Backtracing) : 되추적 이라는 의미. 이전 단계로 거슬러 올라가 다른 가능성을 찾는 방법. 모든걸 찾아보는 점에서는 브루트포스와 비슷하나 그 중에서도 가능성이 있는 것만 찾아보는 가지치기 기법을 사용. (조건을 맞출 수 없는 경우 그 경우를 제외시키는 방법)

 

백트래킹은 보통 경로탐색 알고리즘을 통해서 구현한다고 한다.

 

 

경로탐색 알고리즘이다. 여기엔 두가지 방법이 있다.

 

- 너비 우선 탐색 (Breadth-First Search : BFS)

루트노드에서부터 가까운 노드들을 순서대로 탐색하는 방법이다. 때문에 그래프의 층별로 탐색하는 형태를 띈다.

-> 한번 거친 노드 순서를 저장한 후 다시 꺼내는 선입선출 방식으로 진행 ->  큐 자료구조 사용

graph = {
    '5': ['3', '7'],
    '3': ['2', '4'],
    '7': ['8'],
    '2': [],
    '4': ['8'],
    '8': []
}

visited = []  # 방문 노드 기록
queue = []     # 큐 초기화


def bfs(visited, graph, node):  # function for BFS
    visited.append(node)
    queue.append(node)

    while queue:          # Creating loop to visit each node
        m = queue.pop(0)
        print(m, end=" ")

        for neighbour in graph[m]:
            if neighbour not in visited:
                visited.append(neighbour)
                queue.append(neighbour)


# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, '5')    # function calling

위 코드의 실행 결과는 5 3 7 2 4 8임을 알 수 있다. 이 알고리즘이 적용되는 문제 중 하나는 

https://programmers.co.kr/learn/courses/30/lessons/12978#

코딩테스트 연습 - 배달

프로그래머스의 배달 문제이다.

위 문제의 답은 다음과 같다.

import sys
from collections import deque


def bfs(g, graph, K, N):
    q = deque([g])  # 큐 생성
    table = [sys.maxsize]*(N+1)  # 테이블 생성. 정수 최댓값으로 초기화 <- 0도 유효한 값이기 때문에
    table[1] = 0    # 1에서 1로 가는 길이는 0. 초기화

    while q:
        temp = q.popleft()  # 큐 첫번째 값 초기 -> [1, 0]
        start_point = temp[0] # 1
        cost = temp[1]  # 0

        for i in graph[start_point]:    # 1에서 도달할 수 있는 점들로 loop
            end_point, new_cost = i[0], i[1]    # 도착점, 거리

            if cost + new_cost <= K and cost + new_cost < table[end_point]:
                # 시작 점 까지의 거리( = 현재는 0)와 도착점 까지 거리의 합이
                # K보다 작고, 이 전에 계산한 값 혹은 초기 최댓값 보다 작을 경우에만
                table[end_point] = cost+new_cost
                # 갱신
                q.append([end_point, cost+new_cost])
                # 도착점과 그 점까지의 비용을 새로 전달
    return table


def solution(N, road, K):
    answer = 0
    # make graph
    graph = [[] for _ in range(N+1)]
    for i, j, cost in road:
        graph[i].append([j, cost])
        graph[j].append([i, cost])

    # 정답리스트 받기
    lst = bfs([1, 0], graph, K, N)
    # 맥스 사이즈가 아닌 경우 -> 경로를 찾은 경우
    for i in lst:
        # 카운트
        if i != sys.maxsize:
            answer += 1

    return answer

 

 

- 깊이 우선 탐색 (Depth-First Search : DFS)

경로 하나의 모든 층을 탐색한 후 그 다음 다른 경로의 모든 층을 탐색한다.

-> 재귀 호출이나 스택을 명시하는 방법을 사용

# Using a Python dictionary to act as an adjacency list
graph = {
    '5': ['3', '7'],
    '3': ['2', '4'],
    '7': ['8'],
    '2': [],
    '4': ['8'],
    '8': []
}

visited = set()  # Set to keep track of visited nodes of graph.


def dfs(visited, graph, node):  # function for dfs
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)


# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')

위 코드의 실행 결과는 5 3 2 4 8 7임을 알 수 있다. 이번 문제에서 사용하게 될 알고리즘이다.

import sys


def dfs(x, y, value, length):
    global answer

    # 재귀함수 종료조건
    if length >= 4:
        answer = max(answer, value)
        # 재귀함수 종료를 위한 리턴
        return None

    for d in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nx = x + d[0]
        ny = y + d[1]
        if 0 <= nx < N and 0 <= ny < M and not visit[nx][ny]:
            # 방문 체크
            visit[nx][ny] = True
            # 다음지점 value 더하고 length 더해서 호출
            dfs(nx, ny, value+MAP[nx][ny], length + 1)
            # 방문 체크 해제
            visit[nx][ny] = False


def exception_check(x, y):
    global answer
    # ㅏ ㅜ ㅓ ㅗ 순으로 체크 0,0
    if 0 <= x+2 < N and 0 <= y+1 < M:  # ㅏ
        value = MAP[x][y]+MAP[x+1][y]+MAP[x+2][y]+MAP[x+1][y+1]
        answer = max(answer, value)
    if 0 <= x+1 < N and 0 <= y+2 < M:  # ㅜ
        value = MAP[x][y]+MAP[x][y+1]+MAP[x+1][y+1]+MAP[x][y+2]
        answer = max(answer, value)
    if 0 <= x-1 and x+1 < N and 0 <= y+1 < M:  # ㅓ
        value = MAP[x][y]+MAP[x-1][y+1]+MAP[x][y+1]+MAP[x+1][y+1]
        answer = max(answer, value)
    if 0 <= x-1 and 0 <= y+2 < M:  # ㅗ
        value = MAP[x][y]+MAP[x][y+1]+MAP[x][y+2]+MAP[x-1][y+1]
        answer = max(answer, value)


N, M = map(int, input().split())
MAP = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# DFS 방문 확인
visit = [[False]*M for _ in range(N)]
answer = 0
for i in range(N):
    for j in range(M):

        # 시작지점 방문체크 해제 필요
        visit[i][j] = True
        dfs(i, j, MAP[i][j], 1)
        visit[i][j] = False

        exception_check(i, j)
print(answer)

깊이가 4일 경우로 제한하여 알고리즘을 구현하면 된다. 하지만 ㅗ 모양의 경우에는 깊이가 3일 경우에 해당한다. 그래서 추가적인 조건을 구현하거나 위와같이 별도로 체크하면 된다.

 

알고리즘의 개념이 깊어지면서 점점 코드가 길어지는걸 느낀다.

 

한참 멀었구나 나는..