이코테 유형별 기출문제

구현

외벽 점검

풀이특징

• 원형을 탐색하는 경우 원형데이터 + 길이값을 더한 원형데이터를 붙인 2배의 데이터와 range(시작점, 시작점+길이) 인덱스를 통해 풀 수 있다.
• 친구수가 최대 8명, 각 친구 투입순서에 따라 결과가 달라지므로 8! = 40320 으로 순열을 통해 완전탐색으로 접근.
• 순열: from itertools import permutations
• 각 원형 시작점의 인덱스에 따라 친구들을 순열로 나열하며 각 경우마다 비교.
• 현재 위치와 투입된 친구의 가능길이만큼 더한 탐색가능위치값이 필요.
• 각 취약 지점을 모두 돌면서 탐색가능위치를 벗어나는 경우 친구수를 1씩 증가.
• 친구수가 총 친구수를 넘어서는 경우 탐색을 종료하고, 다음 순열경우를 비교한다.
• 각 취약 지점을 모두 확인한 경우 친구수들을 최종 최소친구수들값에 업데이트 한다.
• 최종 최소친구수들값이 총 친구수를 넘어가는지 여부에 따라 반환.

from itertools import permutations
# 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최솟값을 반환
def solution(n, weak, dist):
    # 취약 지점 개수
    weakSize = len(weak)
    # 원형을 길이 2배로 늘린 일자형태로 변형
    weak = weak + [w + n for w in weak]
    # 투입할 친구수 초기값은 친구수+1
    minCount = len(dist) + 1
    # 취약지점 시작점
    for weakStart in range(weakSize):
        # 친구들 순서나열
        for friends in permutations(dist, len(dist)):
            # 투입할 친구수
            count = 1
            # 점검할 수 있는 마지막 위치 = 취약지점 + 가능길이
            endPoint = weak[weakStart] + friends[count-1]
            
            # 취약지점을 돌면서 확인
            for i in range(0, weakSize):
                index = weakStart + i
                # 범위를 벗어난 경우
                if weak[index] > endPoint:
                    # 새로운 친구 투입
                    count += 1
                    # 더 투입이 불가한 경우 종료
                    if count > len(dist):
                        break
                        
                    # 점검할 수 있는 마지막 위치 = 현재 취약지점 + 가능 길이 업데이트
                    endPoint = weak[index] + friends[count-1]
            
            # 원을 전부 확인한 경우 최소값 업데이트        
            minCount = min(minCount, count)
    # 모든 친구 투입에도 불가한 경우
    if minCount > len(dist):
        return -1
    
    return minCount

DFS/BFS

특정 거리의 도시 찾기

풀이특징

• 간선의 비용이 1로 동일하므로 DFS 사용이 수월
• DFS를 통해 방문하면서 이전 노드의 depth + 1로 설정하며 k값이랑 같은 경우 출력

from collections import deque
# x로부터 출발하여 최단 거리가 정확히 k인 모든 도시의 번호를 출력
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)

distance = [0] * n
q = deque([x-1])

results = []
while q:
    now = q.popleft()
    
    for node in graph[now]:
        if distance[node] == 0:
            q.append(node)
            distance[node] = distance[now]+1
            if distance[node] == k:
                results.append(node)

results.sort()
if len(results) == 0:
    print(-1)
else:
    for i in results:
        print(i+1)

연구소

풀이특징

• 빈칸 중 3곳을 조합을 통해 선택
• 조합의 경우에 따라 바이러스의 DFS 퍼짐
• DFS 종료 후 남은 빈칸수의 개수를 통해 최소값 업데이트

# 안전 영역 크기의 최댓값 출력
# 0: 빈칸, 1: 벽, 2: 바이러스
from itertools import combinations
from collections import deque
import copy
moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]

n, m = map(int, input().split())
graph = []
empty = []
virus = []
for x in range(n):
    row = list(map(int, input().split()))
    graph.append(row)
    for y in range(m):
        if row[y] == 0:
            empty.append((x, y))
        elif row[y] == 2:
            virus.append((x, y))

# 안전 영역의 크기
safeCount = 0
# 바이러스 DFS 함수
def bfs(graph, emptyCount, virus):
    q = deque(virus)

    while q:
        x, y = q.popleft()
        for move in moves:
            nextX, nextY = x+move[0], y+move[1]
            if nextX < 0 or nextX >= n:
                continue
            if nextY < 0 or nextY >= m:
                continue
            # 빈칸인 경우 바이러스 퍼짐
            if graph[nextX][nextY] == 0:
                graph[nextX][nextY] = 2
                emptyCount -= 1
                q.append((nextX, nextY))

    return emptyCount

# 빈칸 세곳을 조합으로 선택 -> 벽 설정
for case in combinations(empty, 3):
    checkGraph = copy.deepcopy(graph)
    for x, y in case:
        checkGraph[x][y] = 1
    # 남은 빈칸수
    emptyCount = len(empty)-3
    # 바이러스 BFS 진행 후
    safe = bfs(checkGraph, emptyCount, virus)
    safeCount = max(safeCount, safe)

print(safeCount)

경쟁적 전염

• 바이러스가 입력된 경우 바이러스 숫자값, 생성된 시각, x, y 값들을 튜플 형식으로 deque 에 넣는다
• deque를 sort 하여 바이러스를 오름차순으로 정렬 한다
• deque 가 빌 때까지 상하좌우 위치를 탐색하며 빈공간이 존재하는 경우 시각+1, 위치값을 deque 에 넣는다
• 시각이 s와 같아진 경우 종료

# s초가 지난 후에 x, y에 존재하는 바이러스의 종류를 출력
from collections import deque
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
n, k = map(int, input().split())

graph = []
virus = []
for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] != 0:
            virus.append((graph[i][j], 0, i, j))

s, x, y = map(int, input().split())

virus.sort()
q = deque(virus)
    
while q:
    v, time, i, j = q.popleft()
    if time == s:
        break
    for move in moves:
        nextX, nextY = i+move[0], j+move[1]
        if nextX < 0 or nextX >= n:
            continue
        if nextY < 0 or nextY >= n:
            continue
        if graph[nextX][nextY] == 0:
            graph[nextX][nextY] = v
            q.append((v, time+1, nextX, nextY))

print(graph[x-1][y-1])