구현 1문제, DFS BFS 2문제

외벽 점검 - X

• 사이트/난이도: 프로그래머스 / 3
• 코드

from itertools import permutations

def solution(n, weak, dist):
    answer = 0
    length = len(weak) # 원래 취약점 개수
    # 둥근 외벽 일자로 펴기
    for i in range(length):
        weak.append(weak[i] + n)
    answer = len(dist) + 1
    
    for start in range(length): # 취약점 시작 지점
        for friends in list(permutations(dist, len(dist))):
            count = 1 # 친구 수
            position = weak[start] + friends[count-1] # 친구의 외벽 점검 종료 위치
            for index in range(start, start+length): # 취약점 모두 점검
                if position < weak[index]:
                    count += 1
                    if count > len(dist):
                        break
                    position = weak[index] + friends[count-1]
            answer = min(answer, count)
    
    if answer > len(dist):
        return -1
    
    return answer

• 느낀점
  • 둥근 외벽을 일자로 펴야 문제 접근이 더 쉬움
  • 취약점을 일자로 펴서 취약점 개수가 다 확인된다면 모두 탐색 가능한 것
  • 친구 수와 취약점 개수가 매우 작으므로 완전탐색을 이용하기
  • 친구를 배치하는 모든 경우의수가 시간복잡도를 넘지 않으므로 순열 이용하기

특정 거리의 도시 찾기

• 사이트/난이도: 백준 / 실버3
• 코드

import sys
from collections import deque

input = sys.stdin.readline
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

INF = 1e9
distance = [INF] * (n+1)
distance[x] = 0

def bfs(start):
    q = deque([start])
    while q:
        now = q.popleft()
        for i in graph[now]:
            if distance[i] == INF:
                distance[i] = distance[now] + 1
                q.append(i)

bfs(x)

check = True
for i in range(1,n+1):
    if distance[i] == k:
        print(i)
        check = False

if check:
    print(-1)

• 느낀점
  • 모든 도로의 거리가 1 일때 BFS 이용시 최단거리 찾을수 있음
  • N, M 의 범위가 상당히 크기 때문에 BFS 사용시 O(N+M) 시간복잡도 나와서 통과 가능
  • BFS이용하여 시작지점에서 부터 최단거리 구하는거기 때문에 방문하지 않은 도시에 거리를 바로 세팅해주면 그게 최단거리임

연구소

• 사이트/난이도: 백준 / 골드4
• 코드

# 벽 3개 세우기 (조합 이용) -> 바이러스 퍼지기 -> 남은 면적 구하기 
from itertools import combinations
import copy
from collections import deque

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
temp = copy.deepcopy(graph)

wall_list = []
virus_list = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            wall_list.append((i,j))
        if graph[i][j] == 2:
            virus_list.append((i,j))

def virus(graph, virus_list):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    q = deque()
    for virus in virus_list:
        q.append(virus)
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = 2
                q.append((nx,ny))
    return graph
    

def get_result(graph):
    answer = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                answer += 1
    return answer

result = 0
for walls in list(combinations(wall_list, 3)):
    temp = copy.deepcopy(graph)
    for x,y in walls:
        temp[x][y] = 1
    temp = virus(temp, virus_list)
    result = max(result, get_result(temp))
print(result)

• 느낀점
  • 연구소의 n, m 의 범위가 매우 작아서 완탐을 통해 벽세우기 진행하고 바이러스 확산은 bfs를 통해 진행했음
  • 답지 풀이에서는 dfs 를 통해 벽세우기를 하고 바이러스 확산도 dfs를 통해 하는것을 확인
  • 근데 이렇게하면 시간초과 나던데 아마 DFS보다 BFS가 일반적으로 더 빨라서 그런거 같음