넌 과감해질 필요가 있어

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw

문제 분석

target 이상이면서 가장 작은 조합을 구하고, 조합의 합과 target의 차이를 return 하라.

접근

N = 20이므로, 백트래킹으로 풀이하면 2 ** 20 ~= 1,000,000 정도일 것이다.
총합이 target 이상이 되면, target과의 차이를 현재 result 값과 비교하여 갱신한다.

모든 원소에 대하여 (추가하거나 / 추가하지 않거나)의 경우를 고려하고, 모든 원소를 탐색하면 result를 갱신한다.

코드

def solve(i, total):
    global n, target, res

    if i == n:
        if total >= target:
            res = min(res, total - target)
        return

    solve(i + 1, total + heights[i])
    solve(i + 1, total)


T = int(input())
for tc in range(T):
    n, target = map(int, input().split())
    heights = list(map(int, input().split()))
    res = 1e9
    solve(0, 0)
    print(f'#{tc + 1} {res}')

간단한 코드이지만, 2 * n개의 경우의 수를 고려하는 백트래킹 문제의 뼈대 코드인 듯하다. 

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV

문제 분석

시작점부터 도착점까지 가장 빠른 길을 찾아야 한다. -> BFS
섬(1)은 지나갈 수 없다.
소용돌이(2)는 지나갈 수 없다. 다만 한 번 통과한 경우 지나갈 수 있다.
    소용돌이(2)는 0초부터 시작해서 2초 동안 유지되고 1초 동안 잠잠해지는 패턴을 반복한다.

접근

BFS 탐색을 하다가 소용돌이를 만났을 때는 판단을 해야 한다.
    방문한 위치인 경우 -> 지날 수 있다
    방문하지 않은 위치인 경우
        time % 3 == 2인 경우, 지날 수 있다
            이때 2를 0으로 바꿔야 한다. 한 번 방문한 뒤에는 언제든 지나갈 수 있기 때문에.
        나머지의 경우, 지날 수 없다.

BFS 탐색을 하는 경우
    큐에는 (x, y, time)이 담겨야 한다.
        그래야 최단 경로를 판단할 수 있기 때문에
    visited 배열은 (x, y, time)의 원소가 완벽하게 같은 경우 걸러낸다.

    4방향 탐색이 아니라, 가만히 있기를 포함한 5방향 탐색이기 때문에, 방문 여부를 결정하기 위해 time이 필요하다.

코드

from collections import deque

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

def bfs(a, b, time):
    q = deque()
    q.append((a, b, time))
    visited = []
    visited.append((a, b, time))

    while q:
        x, y, t = q.popleft()

        if x == ex and y == ey:
            return t

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if matrix[nx][ny] == 1:
                continue

            if matrix[nx][ny] == 2:
                if t % 3 == 2:
                    matrix[nx][ny] = 0
                    q.append((nx, ny, t + 1))
                    visited.append((nx, ny, t + 1))
                else:
                    continue

            if (nx, ny, t + 1) not in visited:
                q.append((nx, ny, t + 1))
                visited.append((nx, ny, t + 1))


testCase = int(input())

for tc in range(testCase):
    n = int(input())
    matrix = [list(map(int, input().split())) for _ in range(n)]
    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())

    result = bfs(sx, sy, 0)
    print(f"#{tc + 1} {result}")

swea에서 해당 문제의 python 제출을 허용하지 않아, 정확한 정답 여부는 알 수 없다.

코테에서 유사한 문제를 풀었던 경험이 있어 어렵지 않게 풀었다.

"제자리에 있기"를 탐색 방향에 포함하는 것이 까다로운데, 시간까지 포함한 visited 배열로 관리하면 풀이할 수 있다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc

문제 분석

지뢰찾기 형태의 2차원 배열.

지뢰가 아닌 곳을 모두 오픈하기 위한 최소 클릭 수를 구하라.

단, 주변의 지뢰 개수가 0인 곳을 클릭하면 주변 위치까지 연쇄적으로 오픈된다.

접근

DFS 혹은 BFS가 적절하다.

최소 값을 구하는 문제이므로 BFS로 진행하자.

최소가 되게 하는 클릭 수를 구하는 것이 까다롭다.

그러나 몇 가지 케이스를 상상하다보면 다음을 알 수 있다.

• 값이 0인 곳들이 인접한 경우, 아무거나 클릭해도 모두가 연쇄적으로 클릭된다.
• 0인 곳을 모두 클릭하고 나면, 나머지 원소는 모두 일일이 클릭해야 한다.

첫 번째 탐색 

• 행렬의 모든 원소에 인접 지뢰 개수 표시 

두 번째 탐색 

• 값이 0인 원소는 주변을 방문 처리
• 방문 처리 중에 만나는 값이 0인 원소는 q에 삽입 후 탐색
• 그렇지 않은 원소는 방문 처리만 

세 번째 탐색 

• 남은 .의 개수 세기

코드

from collections import deque

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

def openMatrix(x, y):
    tmp = 0
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue
        if matrix[nx][ny] == "*":
            tmp += 1
    
    matrix[x][y] = tmp


def clickZeroElement(a, b):

    q = deque()
    q.append([a, b])
    matrix[a][b] = "*"

    while q:
        x, y = q.popleft()

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if matrix[nx][ny] == 0:
                q.append([nx, ny])
                matrix[nx][ny] = "*"
            
            elif matrix[nx][ny] != "*":
                matrix[nx][ny] = "*"

testCase = int(input())

for tc in range(testCase):
    n = int(input())
    matrix = [list(input()) for _ in range(n)]
    total = 0

    for i in range(n):
        for j in range(n):
            if matrix[i][j] == ".":
                openMatrix(i, j)
    
    for i in range(n):
        for j in range(n):
            if matrix[i][j] == 0:
                clickZeroElement(i, j)
                total += 1
    
    for i in range(n):
        for j in range(n):
            if matrix[i][j] != "*":
                total += 1
    
    print(f"#{tc + 1} {total}")

전형적인 삼성 스타일의 문제인 듯하다.

그래도 아주 어렵지는 않다.

클릭 수가 최소가 되게 하는 방법을 고민하다보면, 완전 탐색으로는 불가능하다는 것을 알게 된다.

그 상태에서 문제의 조건에 집중하면 풀이에 접근할 수 있게 된다.

직관적으로도 지뢰찾기 게임을 할 때 0부터 클릭하지 않는가.

참고

https://heo-it-til.tistory.com/entry/SWEA-D4-%ED%8C%8C%ED%95%91%ED%8C%8C%ED%95%91-%EC%A7%80%EB%A2%B0%EC%B0%BE%EA%B8%B01868-Python