구현 vs 완전탐색 vs BFS/DFS

구현 > 완전탐색 > BFS/DFS

1) 구현

• 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램을 작성하는 과정
• 동일한 알고리즘이라면 더 간결하고 효율적으로 작성한 코드가 잘 작성된 코드

2) 완전탐색

• 구현의 대표적인 알고리즘 문제 유형(완전탐색, 시뮬레이션)
• 완전탐색: 모든 경우의 수를 빠짐없이 다 계산하는 해결방법
• 완전탐색 적용: 반복문, 재귀함수, 예외 케이스 모두 확인 --> DFS/BFS 알고리즘 이용, 문제해결

• 완전탐색: 전체 데이터의 개수가 100만 개 이하일때 완전탐색 사용하는 것이 적절함.

# 예제 4-2 시각
h = int(input())

count = 0
for i in range(h + 1):
	for j in range(60):
    	for k in range(60):
        	# 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
            	count += 1
print(count)

# 왕실의 나이트
# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

result = 0
for step in steps:
	next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 다운
    # 체스판과 같은 8 × 8 좌표 평면으로 표현(범위)
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)

def souliton(answer):
	answer = []
    supo = [[1, 2, 3, 4, 5], [2, 1, 2, 3, 2, 4, 2, 5], [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]]
    right = [0, 0, 0]
    
    for i in range(len(supo)):
    	for j in range(len(answers)):
        	n = len(supo[i])
            if answers[j] == supo[i][j%n]
            	right[i] += 1
                
    for idx, score in enumerate(right):
    	if score == max(right):
        	answer.append(idx+1)
return answer

-> 그리디 알고리즘과 구현 알고리즘의 차이보다, 하나의 문제에 구현과 그리디 유형이 함께 포함된 형태로 출제되는 경우가 많음.

3) 시뮬레이션

• 구현의 대표적인 알고리즘 문제 유형(완전탐색, 시뮬레이션)
• 시뮬레이션: 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮겨야 하는 유형
• 시뮬레이션 적용 : 원소 나열의 모든 경우의 수를 고려해야 하는 상황 -> 순열, 조합 라이브러리( itertools로 쉽게 구현 가능)

• 문제형태 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형

# 예제 4-1 상하좌우
n = int(input())
x, y = 1, 1
plans = input().split()

#L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

for plan in plans:
	#이동 후 좌표 구하기
	for i in range(len(move_typeds)):
    	if plan == move_types[i]:
        	nx = x + dx[i]
            ny = y + dy[i]
     # 공간을 벗어나느 경우 무시-> [이부분 생각 못함.]
     if nx < 1 or ny < 1 or nx > n or ny > n:
     	continue
     # 이동 수행
     x, y = nx, ny
print(x, y)

# 게임개발 -> 전형적인 시뮬레이션
# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0]*m for_in range(n)]
# 현재 캐릭터의 x좌표, y좌표, 방향을 입력받기
x, y, direction = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리

# 전체 맵 정보를 입력받기
array = []
for i in range(n):
	array.append(list(map(int, input().split())))
    
# 북, 동, 남, 서 방향 정의    
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 회전
def turn_left():
	global direction
    direction -= 1
    if direction == -1:
    	direction = 3

# 시뮬레이션 시작
count = 1
turn_time = 0
while True:
	# 왼쪽으로 회전
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[nx][ny] == 0 and array[nx][ny] == 0:
    	d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
    	turn_time += 1
    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4:
    	nx = x - dx[direction]
        ny = y - dy[direction]
        # 뒤로 갈 수 있다면 이동하기
        if array[nx][ny] == 0:
        	x = nx
            y = ny
        # 뒤가 바다로 막혀있는 경우
        else:
        	break
        turn_time = 0
 
 # 정답 출력
 print(count)

4) BFS/DFS 구현예제 -> 시뮬레이션+완전탐색(BFS/DFS) 합쳐진 문제

[이코테] DFS/BFS_미로탈출

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(map(int, input())))
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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 = x + dy[i]
        # 미로 찾기 공간을 벗어난 경우 무시
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
        	continue
        # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
        if graph[nx][ny] == 1:
        	graph[nx][ny] = graph[x][y] + 1
            queue.append((nx, ny))
     # 가장 오른쪽 아래까지의 최단 거리 반환
     return graph[n - 1][m - 1]
     
print(bfs(0, 0))

[이코테] BFS/DFS_연구소

n, m = map(int, input().split())
data = [] # 초기 맵 리스트
temp = [[0] * m for _ in range(n)] # 벽을 설치한 뒤의 맵 리스트

for _ in range(n):
    data.append(list(map(int, input().split())))

# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

# 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                # 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
                temp[nx][ny] = 2
                virus(nx, ny)

# 현재 맵에서 안전 영역의 크기 계산하는 메서드
def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

# 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매 번 안전 영역의 크기 계산
def dfs(count):
    global result
    # 울타리가 3개 설치된 경우
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        # 각 바이러스의 위치에서 전파 진행
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        # 안전 영역의 최대값 계산
        result = max(result, get_score())
        return
    # 빈 공간에 울타리를 설치
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1

dfs(0)
print(result)