문장이 그냥 회문이면 0, 글자 하나만 뺐을 때 회문이면 1을, 둘 다 아니면 2를 출력하는 문제이다. 처음에는 한쪽에서부터 올라가면서 절반쯤 도달했을 때 문장 뒤집어서 비교할까 싶다가 하단의 알고리즘 분류에 "투 포인터"라고 되어 있어서 투 포인터로 접근했다.

Python

import sys

input = sys.stdin.readline

n = int(input())

sen = [input().strip() for _ in range(n)]

for s in sen:
  l = len(s)
  start = 0
  end = l - 1

  counta = 0
  while start <= end:
    if counta > 1:
      break

    if s[start] == s[end]:
      start += 1
      end -= 1
    elif start+1 <= end and s[start+1] == s[end]:
      start += 1
      counta += 1
    elif start <= end - 1 and s[start] == s[end - 1]:
      end -= 1
      counta += 1
    else:
      counta = 2

  start = 0
  end = l - 1
  countb = 0
  while start <= end:
    if countb > 1:
      break
    if s[start] == s[end]:
      start += 1
      end -= 1
    elif start <= end - 1 and s[start] == s[end - 1]:
      end -= 1
      countb += 1
    elif start+1 <= end and s[start+1] == s[end]:
      start += 1
      countb += 1
    else:
      countb = 2



  if counta == countb == 2:
    print(2)
  elif counta * countb == 2 or counta * countb == 1:
    print(1)
  else:
    print(0)

문장 양 끝에서부터 중앙으로 오면서 만약에 둘이 다르다면, 서로 한 칸 앞과 또 비교하면서 한 칸 앞이 같다면 count를 추가하고, 각자의 한 칸 앞도 다르다면 2로 처리했다.

매 반복마다 count가 2 이상이 되면 멈추도록 했다.

처음에 실패했는데, start+1과 end를 먼저 비교했기 때문이었다.

baaba

같은 경우 baab로 유사회문이 되는데, start+1을 먼저 비교해서 aaba로 인식 되는 문제가 있었다.

그래서 start+1먼저일 때 한 번, end-1먼저 일 때 한 번 이렇게 두 번 반복문을 실행했다.

count가 둘 다 2라면 2를, 둘 중 하나 이상이 1이라면 1을, 그것도 아니면 0을 출력했다.

from collections import defaultdict

def solution(board, skill):
    answer = 0

    space = defaultdict(int)

    total = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]

    for t, r1, c1, r2, c2, degree in skill:
        degree = -degree if t == 1 else degree
        total[r1][c1] += degree
        total[r1][c2 + 1] += -degree
        total[r2 + 1][c1] += -degree
        total[r2 + 1][c2 + 1] += degree

    for i in range(len(board)):
        for j in range(1, len(board[0])):
            total[i][j] += total[i][j - 1]

    for j in range(len(board)):
        for i in range(1, len(board)):
            total[i][j] += total[i - 1][j]

    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] + total[i][j] > 0:
                answer += 1
    return answer

import heapq

def solution(food_times, k):
    answer = -1
    hq = []
    for i in range(len(food_times)):
        heapq.heappush(hq, (food_times[i], i+1))      
    length = len(hq)
    pre = 0  
    while hq:
        diff = (hq[0][0] - pre) * length
        if diff <= k:
            k -= diff
            length -= 1
            pre, _ = heapq.heappop(hq)
        else:
            idx = k % length
            answer = hq[idx][1]
            break
    return answer

아래, 좌우로만 갈 수 있는 로봇을 조종해서 가장 큰 점수를 얻어서 오른쪽 아래로 도달하는 문제이다.

Python

시도 1 - 실패

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())

mars = list(list(map(int, input().split())) for _ in range(n))

dp = [[-1000] * m for _ in range(n)]

dp[0][0] = mars[0][0]
for i in range(1, n):
    dp[0][i] = mars[0][i] + dp[0][i - 1]

# 점화식
# dp[y][x] = mars[y][x] + max(dp[y-1][x], dp[y][x+1], dp[y][x-1])

dy = [-1, 0, 0]
dx = [0, 1, -1]
visited = [[True] * m for _ in range(n)]

visited[-1][-1] = False


def dfs(sy, sx, visited, dp):
    if dp[sy][sx] != -1000:
        return dp[sy][sx]

    now = mars[sy][sx]

    next = -1000

    for d in range(3):
        ny = sy + dy[d]
        nx = sx + dx[d]

        if 0 <= ny < n and 0 <= nx < m and visited[ny][nx]:
            visited[ny][nx] = False
            tmp = dp[ny][nx]
            next = max(next, dfs(ny, nx, visited, dp))
            visited[ny][nx] = True
            dp[ny][nx] =tmp

    dp[sy][sx] = max(dp[sy][sx], now + next)
    return dp[sy][sx]


print(dfs(n - 1, m - 1, visited, dp))

DFS로 풀어보려했다. 재방문을 방지하고 다른 방향에서 계산한 dp가 영향을 주지 않도록 매번 dp를 초기화 해주었다. 그리고 시간초과로 실패했다.

시도 2

https://wooono.tistory.com/605 이 글의 도움을 받아 해결하였다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
dp = list(list(map(int, input().split())) for _ in range(n))

for i in range(1, m):
    dp[0][i] += dp[0][i - 1]

# 위에서 아래로만 갈 수 있기에 그렇게 진행
# 1번 idx 이후 행별로는 좌우 갚 비교하기
for i in range(1, n):
    ltr = dp[i][:]
    rtl = dp[i][:]

    # 왼쪽에서 오른쪽
    for j in range(m):
        if j == 0:
            ltr[j] += dp[i - 1][j]
        else:
            ltr[j] += max(dp[i - 1][j], ltr[j - 1])

    # 오른쪽에서 왼쪽
    for j in reversed(range(m)):
        if j == m - 1:
            rtl[j] += dp[i - 1][j]
        else:
            rtl[j] += max(dp[i - 1][j], rtl[j + 1])

    for j in range(m):
        dp[i][j] = max(ltr[j], rtl[j])

print(dp[-1][-1])

위에서 아래로만 진행할 수 있기에 전체 진행방향을 그렇게 제한하고, 각 행별로 왼쪽과 오른쪽 각각 진행만 저장할 배열을 만들고, 진행하면서 위vs왼 그리고 위 vs 오른 이렇게 비교했다. 마지막으로 두 진행방향에 대한 배열을 비교해서 최대값만 남겼다.

문제는 통과했는데 풀리지 않는 의문이 있었다.

dp[i][j]가 최대가 되기 위해서는 dp[i][[j-1]을 거쳐야하고, dp[i][[j-1]이 최대가 되기 위해서 dp[i][j]를 거쳐야한다면 모순이 아닌가?

GPT한테 물어봤는데 실제로 그런 샘플도 주었다.

mars = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

이 경우 첫번째 행은 오른쪽으로만 갈 수 있기에

[1, 3, 6]

이되고

두번째 행은 왼쪽에서 오른쪽으로 패스(ltr 계산) ltr[0] = mars[1][0] + dp[0][0] = 4 + 1 = 5 ltr[1] = mars[1][1] + max(dp[0][1], ltr[0]) = 5 + max(3, 5) = 10 ltr[2] = mars[1][2] + max(dp[0][2], ltr[1]) = 6 + max(6, 10) = 16

오른쪽에서 왼쪽으로 패스(rtl 계산) rtl[2] = mars[1][2] + dp[0][2] = 6 + 6 = 12 rtl[1] = mars[1][1] + max(dp[0][1], rtl[2]) = 5 + max(3, 12) = 17 rtl[0] = mars[1][0] + max(dp[0][0], rtl[1]) = 4 + max(1, 17) = 21

이렇게 계산이 되어 최종적으로

[21, 17, 16]

이 된다. 여기서 dp[1][2]는 오른쪽 방향의 연산을, dp[1][1]은 왼쪽방향의 연산을 선택했고, 선택에서도 각각 dp[1][1]을 거치고, dp[1][2]를 거치는 방향을 선택했다.

이 결과가 모순이 아닌지 의문이 들었다.

GPT는 두 연산이 독립적이기에 모순이 아니라고 했지만 의문이 드는 것이

그럼 dp[i][j]가 최대가 되기 위해서 dp[i][[j-1]이 최대일 필요는 없다는 말일까?

라는 의문이 생겼다. GPT의 답변은 특정 셀의 최대값을 각 방향이 독립적으로 계산하고 그 결과만 저장하기에 서로 영향을 주지 않는다고 하였다. 그러니까 dp[i][j]에는 어찌됐건 최대값만 저장하고 그 다음 셀로 가기위한 점수만 제공해준다고 이해하면 될 것 같은데 더 생각을 해봐야겠다.

아래, 좌우로만 갈 수 있는 로봇을 조종해서 가장 큰 점수를 얻어서 오른쪽 아래로 도달하는 문제이다.

Python

시도 1 - 실패

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())

mars = list(list(map(int, input().split())) for _ in range(n))

dp = [[-1000] * m for _ in range(n)]

dp[0][0] = mars[0][0]
for i in range(1, n):
    dp[0][i] = mars[0][i] + dp[0][i - 1]

# 점화식
# dp[y][x] = mars[y][x] + max(dp[y-1][x], dp[y][x+1], dp[y][x-1])

dy = [-1, 0, 0]
dx = [0, 1, -1]
visited = [[True] * m for _ in range(n)]

visited[-1][-1] = False


def dfs(sy, sx, visited, dp):
    if dp[sy][sx] != -1000:
        return dp[sy][sx]

    now = mars[sy][sx]

    next = -1000

    for d in range(3):
        ny = sy + dy[d]
        nx = sx + dx[d]

        if 0 <= ny < n and 0 <= nx < m and visited[ny][nx]:
            visited[ny][nx] = False
            tmp = dp[ny][nx]
            next = max(next, dfs(ny, nx, visited, dp))
            visited[ny][nx] = True
            dp[ny][nx] =tmp

    dp[sy][sx] = max(dp[sy][sx], now + next)
    return dp[sy][sx]


print(dfs(n - 1, m - 1, visited, dp))

DFS로 풀어보려했다. 재방문을 방지하고 다른 방향에서 계산한 dp가 영향을 주지 않도록 매번 dp를 초기화 해주었다. 그리고 시간초과로 실패했다.

시도 2

https://wooono.tistory.com/605 이 글의 도움을 받아 해결하였다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
dp = list(list(map(int, input().split())) for _ in range(n))

for i in range(1, m):
    dp[0][i] += dp[0][i - 1]

# 위에서 아래로만 갈 수 있기에 그렇게 진행
# 1번 idx 이후 행별로는 좌우 갚 비교하기
for i in range(1, n):
    ltr = dp[i][:]
    rtl = dp[i][:]

    # 왼쪽에서 오른쪽
    for j in range(m):
        if j == 0:
            ltr[j] += dp[i - 1][j]
        else:
            ltr[j] += max(dp[i - 1][j], ltr[j - 1])

    # 오른쪽에서 왼쪽
    for j in reversed(range(m)):
        if j == m - 1:
            rtl[j] += dp[i - 1][j]
        else:
            rtl[j] += max(dp[i - 1][j], rtl[j + 1])

    for j in range(m):
        dp[i][j] = max(ltr[j], rtl[j])

print(dp[-1][-1])

위에서 아래로만 진행할 수 있기에 전체 진행방향을 그렇게 제한하고, 각 행별로 왼쪽과 오른쪽 각각 진행만 저장할 배열을 만들고, 진행하면서 위vs왼 그리고 위 vs 오른 이렇게 비교했다. 마지막으로 두 진행방향에 대한 배열을 비교해서 최대값만 남겼다.

문제는 통과했는데 풀리지 않는 의문이 있었다.

dp[i][j]가 최대가 되기 위해서는 dp[i][[j-1]을 거쳐야하고, dp[i][[j-1]이 최대가 되기 위해서 dp[i][j]를 거쳐야한다면 모순이 아닌가?

GPT한테 물어봤는데 실제로 그런 샘플도 주었다.

mars = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

이 경우 첫번째 행은 오른쪽으로만 갈 수 있기에

[1, 3, 6]

이되고

두번째 행은 왼쪽에서 오른쪽으로 패스(ltr 계산) ltr[0] = mars[1][0] + dp[0][0] = 4 + 1 = 5 ltr[1] = mars[1][1] + max(dp[0][1], ltr[0]) = 5 + max(3, 5) = 10 ltr[2] = mars[1][2] + max(dp[0][2], ltr[1]) = 6 + max(6, 10) = 16

오른쪽에서 왼쪽으로 패스(rtl 계산) rtl[2] = mars[1][2] + dp[0][2] = 6 + 6 = 12 rtl[1] = mars[1][1] + max(dp[0][1], rtl[2]) = 5 + max(3, 12) = 17 rtl[0] = mars[1][0] + max(dp[0][0], rtl[1]) = 4 + max(1, 17) = 21

이렇게 계산이 되어 최종적으로

[21, 17, 16]

이 된다. 여기서 dp[1][2]는 오른쪽 방향의 연산을, dp[1][1]은 왼쪽방향의 연산을 선택했고, 선택에서도 각각 dp[1][1]을 거치고, dp[1][2]를 거치는 방향을 선택했다.

이 결과가 모순이 아닌지 의문이 들었다.

GPT는 두 연산이 독립적이기에 모순이 아니라고 했지만 의문이 드는 것이

그럼 dp[i][j]가 최대가 되기 위해서 dp[i][[j-1]이 최대일 필요는 없다는 말일까?

라는 의문이 생겼다. GPT의 답변은 특정 셀의 최대값을 각 방향이 독립적으로 계산하고 그 결과만 저장하기에 서로 영향을 주지 않는다고 하였다. 그러니까 dp[i][j]에는 어찌됐건 최대값만 저장하고 그 다음 셀로 가기위한 점수만 제공해준다고 이해하면 될 것 같은데 더 생각을 해봐야겠다.

불량 사용자 목록에 글자 일부 가려져있고, 전체 사용자 ID가 있을 때 나올 수 있는 불량 사용자 경우의 수를 구하는 문제이다.

Python

from collections import defaultdict

def solution(user_id, banned_id):
    answer = 0
    pos = defaultdict(list)

    for bidx, bid in enumerate(banned_id):
        for idx, uid in enumerate(user_id):
            if (chk_banned(uid, bid)):
                pos[bidx].append(idx)
    ans = set()
    dfs(0, pos, set(), ans)
    return len(ans)

def chk_banned(uid, bid):
    if len(uid) != len(bid):
        return False
    for i in range(len(uid)):
        if bid[i] == '*' or uid[i] == bid[i]:
            continue
        else:
            return False
    return True

def dfs(now, pos, used, ans):
    if now not in pos:
        u = list(used)
        u.sort()
        ans.add(tuple(u))
        return 
    for uid in pos[now]:
        if uid not in used:
            used.add(uid)
            dfs(now + 1, pos, used, ans)
            used.remove(uid)

먼저 uid와 bid를 점검하는 함수를 만들었다. 그래서 그것을 기반으로 각 banned_id에 적용가능한 uid를 딕셔너리로 저장했다.

그러고 나서 dfs함수를 통해서 banned_id의 index 순서대로 들어가면서 나올 수 있는 경우를 탐색했다.

문제의 조건 중에서 목록 순서 상관없이 아이디 내용이 동일하면 같은 것으로 처리한다고 했기에 마지막에 used 집합을 정렬된 튜플로 만들어서 ans 집합에 추가했다.

마지막으로 dfs가 끝나면 ans 집합의 길이를 반환했다.

예전같으면 solution 함수 안에 다 넣거나 dfs만 함수로 만들었을 텐데 라피신을 하고 나니까 함수가 너무 길어지지 않게 기능별로 함수를 쪼개는 습관이 생긴 것 같다. 앞으로 이런 방향으로 코드 짜야겠다.

1과 0으로된 2차원 리스트에서 가장 큰 직사각형을 구하는 문제이다.

코드 1 - 실패

처음에는 BFS로 연결된 점의 집합을 구한 뒤에 각각 x와 y들의 차가 최소인 지점을 찾으면 만족하는 직사각형이 되겠거니 했다.

from collections import defaultdict

class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        r = len(matrix)
        c = len(matrix[0])

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

        ans = 400000000

        for i in range(r):
            for j in range(c):
                if matrix[i][j] == "1":
                    matrix[i][j] = "0"
                    que = [(i, j)]

                    xs = defaultdict(list)
                    ys = defaultdict(list)

                    idx = 0

                    xs[j].append(i)
                    ys[i].append(j)

                    while idx < len(que):
                        y, x = que[idx]
                        idx += 1

                        for d in range(r):
                            ny = y + dy[d]
                            nx = x + dx[d]
                            if 0 <= ny < r and 0 <= nx < c and matrix[ny][nx] == "1":
                                matrix[ny][nx] = "0"
                                que.append((ny, nx))
                                xs[nx].append(ny)
                                ys[ny].append(nx)
                    minX = 4000
                    minY = 4000
                    for x in xs.values():
                        minX = min(max(x) - min(x) + 1, minX)

                    for y in ys.values():
                        minY = min(max(y) - min(y) + 1, minY)
                    print(minY * minX, minY, minX, que)
                    ans = min(ans, minY * minX)
        return ans

그런데 문제의 첫 번째 테스트케이스부터 실패했다. 첫 번째 테스트케이스로 내 코드가 구한 답은 3이다. y의 최소 길이는 2번 행만 해당하는 1이되고, x의 최소 길이는 2~4번 열이 해당하는 3이 된다. 그런데 정답은 색이 칠해진 6이다. DP로 할까 하다가 더 편한 BFS로 될 것 같아서 시도했는데 실패하고 말았다.

코드 2

솔루션 중에 히스토그램처럼 접근한 swift코드가 있어서 참고했다.

        r = len(matrix)
        c = len(matrix[0])

        heights = [0] * (c+1)

        ans = 0
        for row in matrix:
            for j in range(c):
                if row[j] == "1":
                    heights[j] += 1
                else:
                    heights[j] = 0

필요한 값을 정의하고, 히스토그램의 높이를 저장할 height라는 리스트를 정의한다. 이때, 오른쪽에서 왼쪽으로 너비를 측정하므로 가장 마지막 원소를 포함시키기 위해서 0을 추가해준다.

행을 돌면서 1인 경우에는 height에 1을 더해주고, 0이면 이때까지 쌓인 높이가 초기화가 됐기에 0을 저장한다.

            stack = []
            for j in range(c+1):
                while stack and heights[j] < heights[stack[-1]]:
                    last = stack.pop()
                    height = heights[last]
                    width = j - 1 - (stack[-1] if stack else -1)
                    ans = max(ans, height * width)
                stack.append(j)

x좌표를 저장할 stack이라는 리스트를 선언한다. 그리고 height를 순회하는데 만약 stack이 비어있다면 추가해준다. heights[j]가 stack에 마지막으로 저장된 높이보다 작으면 스택에 마지막으로 저장된 높이를 기준으로 직사각형의 너비를 계산한다.

너비는 j직전까지는 height[last]의 높이를 가졌을 것이기에 j-1부터 측정한다.

만약 stack에 다른 값이 있다면 해당 x좌표의 높이는 heights[last]보다 작을 것이기에 x좌표까지 측정하고, 만약 값이 없다면 왼쪽 끝까지 측정한다. 매번 너비를 계산할 때마다 최대 너비를 비교해서 업데이트 해주면 답을 구할 수 있게 된다.

from collections import defaultdict

class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        r = len(matrix)
        c = len(matrix[0])

        heights = [0] * (c+1)

        ans = 0
        for row in matrix:
            for j in range(c):
                if row[j] == "1":
                    heights[j] += 1
                else:
                    heights[j] = 0
            stack = []
            for j in range(c+1):
                while stack and heights[j] < heights[stack[-1]]:
                    last = stack.pop()
                    height = heights[last]
                    width = j - 1 - (stack[-1] if stack else -1)
                    ans = max(ans, height * width)
                stack.append(j)
        return ans

코드를 이해하는데 한참이 걸렸다. 파워포인트로 끄적이고 해보니 대충 이해가 가긴 했는데 표시해두고 나중에 다시 풀어봐야겠다.

이렇게 생긴 그래프가 있고 파란색이 출입구, 빨간색이 정상일 때, 등산 코스를 이루는 각 경로의 거리가 최소값인 등산코스 찾는 문제이다.

정상은 한 번만 가야하고, 들어갔던 출입구로 나와야한다.

Python

시도 1 - 실패

from heapq import heappush, heappop
from collections import defaultdict

def solution(n, paths, gates, summits):
    answer = [float('inf'), float('inf')]

    gates_set = set(gates)
    summits_set = set(summits)
    # 거리 합이 최소가 아니라도
    # 거리 한 개의 길이가 최대인게 최소가 되게 해라는거네

    graph = defaultdict(list)
    for a, b, c in paths:
        graph[a].append((b, c))
        graph[b].append((a, c))

    for g in gates:
        intensity = [-1] * (n + 1)
        q = [(0, g, False)] # 정상에 닿았는가
        intensity[g] = 0

        while q:
            cost, now, summit_chk = heappop(q)

            # g에서 출발했는데 다른 게이트 있으면 안 됨
            if now != g and now in gates_set:
                continue

            # 정상에 닿았는데 다른 정상에 가면 안 됨
            if summit_chk and now in summits_set:
                continue

            # 이미 찾은 거리가 새로 계산할 거리보다 작다면 패스
            if 0 <= intensity[now] < cost:
                continue

            for next, d in graph[now]:
                if intensity[next] == -1 or intensity[next] > cost:
                    # 거리합이 중요한 것이 아니라 거리가 중요한거라 더하기 안 하고 그냥 작은 거리로 업데이트 할 것
                    intensity[next] = max(cost, d)
                    if next in summits_set:
                        summit_chk = True
                    heappush(q, (intensity[next], next, summit_chk))
        for s in summits:
            if intensity[s] < answer[1]:
                answer = [s, intensity[s]]
            elif intensity[s] == answer[1] and (s < answer[0]):
                answer[0] = s
    return answer

gate별로 시작하면서 다익스트라를 돌렸다. 등산코스 경로의 최대값을 저장하는 intensity를 만들어서 그거를 기준으로 heap을 만들었다. 다른 출입구에 닿지 않게 조건을 추가하였고, 다른 정상도 안 가게 summit_chk를 만들어서 정상에 닿은 코스일 경우 True를 저장해서 다른 정상에 못 가게 했다.

그리고 다익스트라가 끝나면 intensity가 최소인 정상, 그리고 값이 같으면 정상 번호가 작은 것을 저장하게 했는데 일부 시간초과와 일부 그냥 실패가 결과로 나왔다.

아무래도 모든 게이트에 대해서 모든 정상까지의 거리를 비교한게 시간초과의 원인이 된 것 같다.

시도 2 - 실패

from heapq import heappush, heappop
from collections import defaultdict

def solution(n, paths, gates, summits):
    answer = [float('inf'), float('inf')]

    gates_set = set(gates)
    summits_set = set(summits)

    graph = defaultdict(list)
    for a, b, c in paths:
        graph[a].append((b, c))
        graph[b].append((a, c))

    for g in gates:
        intensity = [-1] * (n + 1)
        q = [(0, g)]
        intensity[g] = 0

        while q:
            cost, now = heappop(q)

            if (now != g and now in gates_set) or 0 <= intensity[now] < cost:
                continue

            for next, d in graph[now]:
                if intensity[next] == -1 or intensity[next] > max(d, cost):
                    intensity[next] = max(cost, d)
                    if next not in summits_set:
                        heappush(q, (intensity[next], next))
                    else:
                        if intensity[next] < answer[1]:
                            answer = [next, intensity[next]]
                        elif intensity[next] == answer[1] and (next < answer[0]):
                            answer[0] = next

    return answer

answer에 값을 비교하는 과정을 다익스트라 안에 넣었다. 정상에 도착하면 heap에 넣는 대신 answer에 거리와 정상 번호를 비교해서 업데이트 하도록 했고, 정상이 아닐 경우에만 que에 해당 지점을 넣었다.

이렇게하니까 15, 16, 17, 23, 25에서 시간초과 발생한 것 외에 전부 정답처리되었다.

시도 3

from heapq import heappush, heappop
from collections import defaultdict

def solution(n, paths, gates, summits):
    answer = [float('inf'), float('inf')]

    gates_set = set(gates)
    summits_set = set(summits)

    graph = defaultdict(list)
    for a, b, c in paths:
        graph[a].append((b, c))
        graph[b].append((a, c))

    q = []
    intensity = [-1] * (n + 1)
    for g in gates:
        heappush(q, (0, g))
        intensity[g] = 0

    while q:
        cost, now = heappop(q)

        if (cost != 0 and now in gates_set) or 0 <= intensity[now] < cost:
            continue

        for next, d in graph[now]:
            if intensity[next] == -1 or intensity[next] > max(d, cost):
                intensity[next] = max(cost, d)
                if next not in summits_set:
                    heappush(q, (intensity[next], next))
                else:
                    if intensity[next] < answer[1]:
                        answer = [next, intensity[next]]
                    elif intensity[next] == answer[1] and (next < answer[0]):
                        answer[0] = next

    return answer

GPT의 도움을 받아 해결했다. 이전 코드처럼 게이트 하나당 다익스트라를 실행하지 않고 동시에 여러 게이트에 대해서 다익스트라를 진행할 수 있었다. 대신, 이렇게하면 어떤 시작점에 대한 최소거리인지 알 수 없게 되는데 어차피 문제에서는 정상과 정상까지의 최단거리만을 요구하였기에 시작점을 알 필요가 없다.

여러 시작점에 대한 최단거리를 구해야할 때, 시작점의 구분이 중요하지 않다면 그냥 heap에 시작점 다 넣고 시작하는 다익스트라를 고려해봐야겠다.

골목길 지날 때마다 돈을 얻거나 잃는데, 수익 최대로 하면서 목적지까지 가는 최적 경로 찾는 문제이다. 벨만-포드 알고리즘의 간선완화를 사용해서 n번 돌면서 수익이 최대가 되도록 설정했고, n+1번부터 수익이 더 해지는 곳이 있다면 사이클이 있는 것으로 판단하고 -1을 출력하도록 했다.

Python

시도 1 - 실패

n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(m)]
dp = [-float("inf")] * (n + 1)
parent = [i for i in range(n + 1)]
chk = False
dp[1] = 0
for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            dp[v] = dp[u] + w
            parent[v] = u

for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            chk = True
            break

if chk:
    print(-1)
else:
    answer = [n]
    next = parent[n]
    while next != parent[next]:
        answer.append(next)
        next = parent[next]
    answer.append(1)
    print(" ".join(map(str, answer[::-1])))

5 5 1 2 -1 2 3 1 3 4 1 4 2 1 2 5 -1

이 테스트 케이스에 대해서 1에서 4로 가는 경로는 최적화가 되었지만 2, 3, 2, 3 사이클 때문에 -1을 출력하는 문제가 있었다. 그래서

if chk:
    reachable = [False] * (n + 1)
    reachable[1] = True
    for _ in range(n):
        for u, v, w in graph:
            if reachable[u]:
                reachable[v] = True
    if reachable[n]:
        visited = [False] * (n + 1)
        answer = [n]
        next = parent[n]
        while next != parent[next]:
            if visited[next]:
                print(-1)
                break
            visited[next] = True
            answer.append(next)
            next = parent[next]
        else:
            answer.append(1)
            print(" ".join(map(str, answer[::-1])))
    else:
        print(-1)

사이클이 발견됐을 때, n에서 1까지 사이클 없이 접근 가능한지 판별하는 코드를 만들었다.

시도 2 - 실패

n, m = map(int, input().split())

# 벨만 포드 알고리즘으로 조져야함.
# 벨만 포드의 간선완화 사용해서 음수 사이클 유무 찾아야한다.
# 그래서 1번에서 n번까지의 최단경로 찾아야함
# 아 아니다 돈 가장 많이 벌면서 갈 수 있는 길 찾아야함.

graph = [list(map(int, input().split())) for _ in range(m)]
dp = [-float("inf")] * (n + 1)
parent = [i for i in range(n + 1)]
chk = False
dp[1] = 0
for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            dp[v] = dp[u] + w
            parent[v] = u

for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            chk = True
            break
if chk:
    reachable = [False] * (n + 1)
    reachable[1] = True
    for _ in range(n):
        for u, v, w in graph:
            if reachable[u]:
                reachable[v] = True
    if reachable[n]:
        visited = [False] * (n + 1)
        answer = [n]
        next = parent[n]
        while next != parent[next]:
            if visited[next]:
                print(-1)
                break
            visited[next] = True
            answer.append(next)
            next = parent[next]
        else:
            answer.append(1)
            print(" ".join(map(str, answer[::-1])))
    else:
        print(-1)
else:
    answer = [n]
    next = parent[n]
    while next != parent[next]:
        answer.append(next)
        next = parent[next]
    answer.append(1)
    print(" ".join(map(str, answer[::-1])))

https://www.acmicpc.net/board/view/136016 의 샘플을 돌렸을 때 2 때문에 -1을 출력해야하지만 경로를 출력하는 문제가 있었다.

그래서 사이클 탐지 후 재검사하는 과정을 그래서

if chk:
    reachable = [False] * (n + 1)
    reachable[1] = True
    for _ in range(n):
        for u, v, w in graph:
            if reachable[u]:
                reachable[v] = True
    if reachable[n]:
        visited = [False] * (n + 1)
        answer = []
        next = n
        while next != 1:
            if visited[next]:
                print(-1)
                break
            visited[next] = True
            answer.append(next)
            next = parent[next]
        else:
            answer.append(1)
            print(" ".join(map(str, answer[::-1])))
    else:
        print(-1)

이렇게 수정했는데 그래도 실패했다.

시도 3 - 다른 코드 참고

n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(m)]

dp = [-float("inf")] * (n + 1)
dp[1] = 0
parent = [i for i in range(n + 1)]
chk = False
for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            dp[v] = dp[u] + w
            parent[v] = u
            if i == n:
                dp[v] = float("inf")

result = []
cur_node = n
if dp[n] == float("inf"):
    print(-1)
else:
    while cur_node != 1:
        result.append(cur_node)
        cur_node = parent[cur_node]
    result.append(1)
    print(" ".join(map(str, result[::-1])))

다른 블로그에서 코드를 참고해서 가져왔다. 로직은 나랑 비슷한데 사이클 탐지부분이 달랐다. 사이클이 탐지되면 탐지된 곳에 최대값을 저장하게했다. 그러면 n번째 탐색 때, 전체 경로를 다시 검사하면서 목적지인 n이 관여하게 된다면 n에 대한 거리는 INF로 업데이트 되고 그러면 마지막에 출력부분에서 걸러지게 되는 것이다.

사이클 유무가 중요한 것이 아니라 목적지가 사이클에 관여했는가가 중요하기에 이전 문제와 방법을 달리 해야했다.

수열 a의 부분수열 중에서, 길이가 2이상 짝수이고, 앞에서부터 2개씩 나눈 부분집합들의 교집합의 원소가 1개 이상인 수열이 있으면 스타수열이라고 할 때 가장 긴 스타수열의 길이를 구하는 문제이다.

Python

시도 - 1 - LIS 방식

def solution(a):
    answer = 2

    if len(a) <= 1:
        return 0

    d = [2]
    x = []

    return answer

def chk_star(list):
    if len(list) <= 1 and len(list) % 2 != 0:
        return False
    chk = [0, 0]
    for i in range(2, len(list)):
        if list[0][0] in list[i]:
            chk[0] += 1
        if list[0][1] in list[i]:
            chk[1] += 1

    if chk[0] == len(list) // 2 or chk [1] == len(list):
        return True
    else:
        return False

만들다만 코드이다. 가장 긴 증가하는 부분수열이 생각나서 앞에서부터 숫자 한 개씩 넣으면서 길이가 짝수이면 chk_star라는 함수를 통해 스타수열인지 확인하고 아니라면 다음 숫자 넣는 방식으로 해볼까 했다. LIS에서는 한 개씩 숫자를 비교하고 판단했는데, 여기서는 숫자 두 개를 넣어서 판단해야하는 차이점이 있었고, 그 두 개도 연속적인 두 개가 아니라 한 개 넣고 한참 뒤에 추가한 한 개가 스타수열이 될 수도 있고 한다는 점에서 시간복잡도가 엄청날 것 같아서 포기했다. chk_star도 최악의 경우 2n번 비교해야하기에 그걸 모든 숫자에 하면 O(n^2)의 복잡도가 날 것 같아서 버렸다.

시도 2 - 숫자 넣어보기

질문하기의 글 중 파이썬 탐욕법적 접근라는 글을 참고했다.

어차피 교집합의 숫자가 한 개이기 때문에 숫자 한 개를 기준으로 앞 뒤에 다른 숫자 한 개 있는지 비교하고 있으면 스타수열의 부분집합으로 간주해서 개수를 더하는 방식으로 최대 길이 구하는 방식이다.

def solution(a):
    answer = -1

    nums_idx = [[] for _ in range(max(a) + 1)]

    for idx, n in enumerate(a):
        nums_idx[n].append(idx)

    for n, idxes in enumerate(nums_idx):
        used = set()
        for i in idxes:
            if (i - 1) >= 0 and (i - 1) not in used and i not in used and a[i] != a[i - 1]:
                used.add(i)
                used.add(i - 1)
            elif (i + 1) < len(a) and (i + 1) not in used and i not in used and a[i] != a[i + 1]:
                used.add(i)
                used.add(i + 1)
        answer = max(answer, len(used))


    return answer

먼저 nums_idx라는 리스트를 만들어서 0부터 최대 숫자만큼의 빈 리스트를 생성했다. 그리고 그 다음 for문을 통해서 각 숫자에 해당하는 리스트에 위치 정보를 저장했다.

이렇게 만든 위치정보를 돌면서 탐색을 시작했는데, used라는 집합을 만들어서 이미 집합 만드는데 사용된 index인지 파악했다.

그 다음 조건문으로는 먼저 왼쪽 원소에 대해서 0이상이고, 사용되지 않았고, i도 사용 안 됐고 둘이 숫자가 서로 다르다면 used에 추가했고 왼쪽 원소가 실패하면 오른쪽 원소에 대해 같은 절차를 진행했다.

마지막으로 이렇게 집합에 추가된 index의 개수를 세서 answer와 비교했다.

이런모양으로 확장되는 모눈종이의 일부를 출력하는 문제이다

Python

1차 시도 - 메모리 초과

r1, c1, r2, c2 = map(int, input().split())

n = max(abs(r1), abs(c1), abs(r2), abs(c2))

# 전체 모눈종이의 너비 혹은 소용돌이의 너비
n = 2 * n + 1

def makeCyclone(n):
    sy, sx = n//2, n//2

    cycle = [[0] * n for _ in range(n)]
    cycle[sy][sx] = 1

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

    d = 0
    l = 1
    number = 2

    while sy < n and sx < n:
        for i in range(l):
            sy = sy + dy[d]
            sx = sx + dx[d]

            if sy >= n or sx >= n:
                break

            cycle[sy][sx] = number
            number += 1
        d = (d + 1) % 4
        if d == 0 or d == 2:
            l += 1

    return cycle

cycle = makeCyclone(n)

r1 += n//2
r2 += n//2
c1 += n//2
c2 += n//2

for i in range(r1, r2+1):
    row = cycle[i]
    print(' '.join(map(str,row[c1:c2+1])))

입력되는 값 중 최대값을 가지고 필요한 전체 모눈종이의 너비를 구한 후, makeCyclone 함수를 통해서 모눈종이를 그렸다. 그리고 일부를 출력했는데 아무래도 5000 * 5000 크기의 모눈종이를 그리게 될 경우에 메모리에 담기에는 너무 컸나보다.

수학적으로 접근할 필요가 있겠다.

시도 2 - 출력 형식 실패

r1, c1, r2, c2 = map(int, input().split())

n = max(abs(r1), abs(c1), abs(r2), abs(c2))

def cal_start(n):
    if n == 0:
        return 1
    return 4 * n * (n - 1) + 2

def cal_number(i, j):
    n = max(abs(i), abs(j))
    start_num = cal_start(n)
    if n == 0:
        return 1
    sy, sx = n-1, n

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

    d = 0

    turningPoint = {(-n, n), (-n, -n), (n, -n)}

    while (dy, dx) != (n, n+1):
        if sy == i and sx == j:
            return start_num

        if (sy, sx) in turningPoint:
            d = (d+1)%4

        sy += dy[d]
        sx += dx[d]
        start_num += 1



ans = [[0] * (c2 - c1 + 1) for _ in range(r2 - r1 + 1)]

for i in range(r1, r2+1):
    for j in range(c1, c2+1):
        ans[abs(i - r1)][abs(j - c1)] = cal_number(i, j)

if len(ans) == 1 and ans[0][0] // 10 == 0:
    print(ans[0][0])
else:
    for a in ans:
        tmp = ""
        for c in a:
            if c//10 == 0:
                tmp += " " + str(c)
            else:
                tmp += str(c)
            tmp += " "

        print(tmp)

네모의 길이 규칙을 먼저 찾아보았다

0 1 2 3 4 1, 3+3+1+1, 5+5+3+3, 7+7+5+5, 9+9+7+7 1, 8 , 16 , 24 , 32

그리고 다음과 같은 수열의 공식을 얻었고

n번째 네모 x(n) = 2 * (2n-1 + 2n+1) = 8n

n번째 네모의 끝점: 4 * (n+1) * n + 1 0: 0 + 1 = 1 1: 4 * 2 * 1 + 1 = 9 2: 4 * 3 * 2 + 1 = 25 3: 4 * 4 * 3 + 1 = 48 + 1 = 49

네모의 끝점을 얻었으니 n번째 네모의 시작점의 숫자는 4 * n * (n-1) + 2가 되는 것을 알 수 있다.

또한, 점이 (i, j)일 때 네모는 max(abs(i), abs(j))을 통해서 몇 번째 네모인지 구할 수 있다.

시작점부터 탐색하기로 결정했다. 탐색했을 때 최악의 경우는 해봐야 49 * 4 * (5000 * 4)일 것이라 판단돼서 아까 2천5백만의 메모리보다는 나을 것 같았다.

turningpoint를 만들어서 여기에 도착할 때마다 방향을 전환하도록 했으며, 탐색 도중 원한는 위치를 찾는다면 해당 위치의 숫자를 반환하도록 했다.

그리고 출력했는데 출력 모양에서 실패했다.

예쁜 모양이라는게 자리 위치까지 맞추라는 것인 줄은 몰랐다.

시도 3

r1, c1, r2, c2 = map(int, input().split())

n = max(abs(r1), abs(c1), abs(r2), abs(c2))

def cal_start(n):
    if n == 0:
        return 1
    return 4 * n * (n - 1) + 2

def cal_number(i, j):
    n = max(abs(i), abs(j))
    start_num = cal_start(n)
    if n == 0:
        return 1
    sy, sx = n-1, n

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

    d = 0

    turningPoint = {(-n, n), (-n, -n), (n, -n)}

    while (dy, dx) != (n, n+1):
        if sy == i and sx == j:
            return start_num

        if (sy, sx) in turningPoint:
            d = (d+1)%4

        sy += dy[d]
        sx += dx[d]
        start_num += 1



ans = [[0] * (c2 - c1 + 1) for _ in range(r2 - r1 + 1)]
maxLen = 0
for i in range(r1, r2+1):
    for j in range(c1, c2+1):
        ans[abs(i - r1)][abs(j - c1)] = cal_number(i, j)
        maxLen = max(len(str(ans[abs(i - r1)][abs(j - c1)])), maxLen)

for line in ans:
    tmp = ""
    for l in line:
        for _ in range(maxLen - len(str(l))):
            tmp += " "
        tmp += str(l) + " "
    print(tmp[:-1])

숫자를 찾으면서 maxLen이라는 변수에 최대 자리수를 저장하였다. 그리고 출력하면서 maxLen에 부족한 만큼 공백을 추가하였고 tmp가 완성됐을 때 출력은 마지막 공백을 제거하여 출력하였다.

시도 4

r1, c1, r2, c2 = map(int, input().split())

width = c2 - c1 + 1
height = r2 - r1 + 1
max_len = 0
nums = [[0] * width for _ in range(height)]

for i in range(height):
    for j in range(width):
        c = c1 + j
        r = r1 + i
        nsq = max(abs(c), abs(r))
        if c == 0 and r == 0:
            nums[i][j] = 1
        elif c == nsq and r != nsq: # 오른쪽 변, 
            nums[i][j] = (2 * nsq - 1) ** 2 + nsq * 2 * 0 + abs(nsq - r)
        elif r == -nsq and c != nsq: # 위쪽변
            nums[i][j] = (2 * nsq - 1) ** 2 + nsq * 2 * 1 + abs(nsq - c)
        elif c == -nsq and r != -nsq: # 왼쪽 변
            nums[i][j] = (2 * nsq - 1) ** 2 + nsq * 2 * 2 + abs(-nsq - r)
        elif r == nsq and c != -nsq: # 아래쪽변
            nums[i][j] = (2 * nsq - 1) ** 2 + nsq * 2 * 3 + abs(-nsq - c)

        max_len = max(max_len, len(str(nums[i][j])))

for n in nums:
    tmp = ""
    for l in n:
        for _ in range(max_len - len(str(l))):
            tmp += " "
        tmp += str(l) + " "
    print(tmp[:-1])

각 사각형의 오른쪽 아래를 계산했다. (0번째 사각형부터 시작) n번째 사각형의 오른쪽 아래는 (2 * n + 1)^2가 되었다. 그러면 n번째 사각형의 시작숫자는 (2 * n - 1) ^ 2 + 1이 된다.

그렇게 해서 각 변에 대한 조건을 나누어서 숫자 범위를 4등분 하였고, 각 변의 기준에서 떨어진 만큼 숫자를 더해서 답을 구하였다.

n-queen 문제이다. DFS로 접근해서 위 행에서부터 퀸을 배치해 나가면서, check라는 함수를 통해서 가로 세로, 대각선에 놓을 수 있는지 판단했다.

Python

n = int(input())

def check(x):

  for i in range(x):
    if row[x] == row[i]:
      return False
    if abs(row[x] - row[i]) == x - i:
      return False
  return True

def dfs(x):
  global result
  if x == n:
    result += 1
  else:
    for i in range(n):
      row[x] = i
      if check(x):
        dfs(x + 1)

row = [0] * n
result = 0
dfs(0)

print(result)

벨만 포드의 간선완화를 구현하는데 문제가 있었지만 통과했다고 우기는 사람을 참교육하기 위해 반례를 찾는 내용이다.

간선완화는 특정 시작점으로부터 n-1번 반복해서 나머지 점까지의 최단 거리를 구하는 방법이다. 여기서 n번째부터 반복을 시작할 때 최단거리가 업데이트 된다면 이거는 음의 사이클이 발생했다는 것으로 판단할 수 있게 된다.

문제에서는 간선 완화를 할 때, n-2번만 반복해서 최단 거리가 하나 덜 구해진 상태이다. 거기서 음수 사이클 검증을 위한 간선완화를 다시 진행할 때 n-1번째 간선완화가 진행되어서 값이 업데이트 되는데, 문제 상황에서는 이거를 음의 사이클에 대한 증거로 판단해서 음의 사이클이 없지만 있다고 결론을 내린 상황이다.

그래서 모든 간선이 음수이고, 사이클이 없는 그래프를 만든다면 반례로 사용할 수 있을 것이다.

Python

n, m = 50, 49

print(n, m)

start = 1

edges = []

for i in range(m):
    a, b, c = start, start + 1, -1
    edges.append((a, b, c))
    start += 1

for e in reversed(edges):
    print(" ".join(map(str, e)))

문제의 조건이 n이 50이상 100 이하여서 n을 50으로 초기화하고 사이클이 생길 수 없게 m을 49로 선언했다.

그리고 1 -> 2, 2 -> 3 이런식으로 일렬로 연결되도록 설정하고 간선의 코스트는 -1로 주었다.

접두사가 가장 비슷한 문자열을 찾는 문제이다. 문자열을 index와 함께 저장하고, 정렬한 후에 앞뒤로 문자열을 비교하면서 가장 큰 문자열을 찾는 방식을 사용했다.

Python

1차 실패

import sys

input = sys.stdin.readline

n = int(input())

words = list(enumerate(list(input().strip() for _ in range(n))))
origin = words[:]
words.sort(key=lambda x:(x[1], x[0]))

maxCnt = 0
answer = (-1, -1)
pre = ""

for i in range(n-1):
    idx = 0
    cnt = 0

    ai, a = words[i]
    bi, b = words[i+1]

    if a == b:
        continue

    while idx < len(a) and i < len(b):
        if a[idx] == b[idx]:
            cnt += 1
        else:
            break
        idx += 1
    if maxCnt < cnt:
        maxCnt = cnt
        answer = (min(ai, bi), max(ai, bi))

pre = origin[answer[0]][1][:maxCnt]

printcount = 0
print1 = ""
for o in origin:
    if printcount == 2:
        break

    if o[1][:maxCnt] == pre and print1 != o[1]:    
        print(o[1])
        printcount += 1
        print1 = o[1]

단어를 정렬하고 앞뒤로 비교하면서 가장 큰 접두사의 길이와 해당 단어들을 기억했다. 그리고 마지막에 해당 접두사를 가진 단어들을 앞에서부터 탐색하면서 두 번 출력했다. 그리고 3%에서 실패했다.

https://www.acmicpc.net/board/view/143309

여기 글의 테스트케이스를 실행했다.

input:
8
a
acd
ab
abc
ace
abd
acf
ade

output:
acd
ace

1차 코드의 출력은 ab, abc가 나왔다. 순서상으로는 acd가 나와야하는데 정렬하면 ab가 먼저 나와서 pre에 ab가 저장된 것 같다.

2차

import sys
input = sys.stdin.readline

n = int(input())

ip = []
for i in range(n):
  ip.append((input().strip(), i))


words = sorted(ip)

ans = [0] * (n)
maxCnt = 0
for i in range(n-1):
    cnt = 0
    a = words[i][0]
    b = words[i+1][0]

    for x in range(min(len(a), len(b))):
      if a[x] == b[x]:
        cnt += 1

    maxCnt = max(cnt, maxCnt)

    ans[words[i][1]] = max(ans[words[i][1]], cnt)
    ans[words[i+1][1]] = max(ans[words[i+1][1]], cnt)

chk = -1
pre = ""
for i in range(n):
  if chk == -1 and ans[i] == maxCnt:
    chk = i
    print(ip[i][0])
    pre = ip[i][0][:maxCnt]
  elif ans[i] == maxCnt and (maxCnt == 0 or pre == ip[i][0][:maxCnt]):
    print(ip[i][0])
    break

그래서 단어별로 최대 접두사의 길이를 저장하고 전체 접두사의 최대 길이를 maxCnt에 저장했다. 그리고 마지막에 maxCnt에 해당하는 단어들 중에서 처음 나오는 단어의 pre를 저장하고, 출력한 후 그 다음 단어들 중에서 pre로 시작하는 첫 번째 단어를 출력했다.

그러나 50%에서 계속 틀렸다. 코드를 살펴봐도 아무런 문제가 없어보였었다.

나중에 다시 보니까 문자열을 비교하는 과정에서 접두사가 같은 구간이 끝나면 멈춰야하는데 멈추지 않고 끝까지 비교해서 발생한 문제 같았다.

import sys
input = sys.stdin.readline

n = int(input())

ip = []
for i in range(n):
  ip.append((input().strip(), i))


words = sorted(ip)

ans = [0] * (n)
maxCnt = 0
for i in range(n-1):
    cnt = 0
    a = words[i][0]
    b = words[i+1][0]

    for x in range(min(len(a), len(b))):
      if a[x] == b[x]:
        cnt += 1
      else:
        break
    maxCnt = max(cnt, maxCnt)

    ans[words[i][1]] = max(ans[words[i][1]], cnt)
    ans[words[i+1][1]] = max(ans[words[i+1][1]], cnt)

chk = -1
pre = ""
for i in range(n):
  if chk == -1 and ans[i] == maxCnt:
    chk = i
    print(ip[i][0])
    pre = ip[i][0][:maxCnt]
  elif ans[i] == maxCnt and (maxCnt == 0 or pre == ip[i][0][:maxCnt]):
    print(ip[i][0])
    break

중간에 달라지면 멈추도록 break를 넣어주니까 정상적으로 동작했다.

이진트리에 양과 늑대가 있고 탐색하면서 양과 늑대를 줍는데, 양의 수가 늑대를 항상 초과하게 주울 때 양을 최대 몇 마리 주울 수 있는지 구하는 문제이다.

Python

시도 1 - 실패

def solution(info, edges):
    answer = [0]

    adj = [[] for _ in range(len(info))]

    for a, b in edges:
        adj[a].append(b)
        # adj[b].append(a)

    dfs(0, adj, info, 1, 0, answer, [])
    return answer[0]

def dfs(start, adj, info, sheep, wolves, answer, track):

    if wolves >= sheep:
        return -1

    answer[0] = max(answer[0], sheep)

    search = set(adj[start] + list(track))
    visited = set()
    while search:
        next = search.pop()
        chk = dfs(next, adj, info, sheep + abs(info[next] - 1), wolves + info[next], answer, search)
        if chk == -1 and next not in visited:
            search.add(next)
            visited.add(next)

먼저 단방향 인접 리스트를 만들고 dfs 함수를 만들었다. dfs에서는 지금 주운 양과 늑대의 수를 비교하고 늑대가 양보다 크거나 같다면 -1을 반환하도록 했다. 그렇지 않다면 지금까지 주운 양과 answer를 비교해서 최대값을 업데이트 해주었다.

dfs의 파라미터로 track을 두었는데 이는 상위 노드에서 탐색하지 않았거나 늑대가 "그때 당시에는" 더 많아서 탐색에 실패한 노드를 저장하는 곳이다. 그래서 현재 노드와 연결된 곳 모두 탐색하고 상위 노드에서 탐색하지 않은 곳을 다시 가도록 하기 위해 track을 두었다. 그리고 search라는 집합에 인접노드와 미탐색 노드를 같이 저장하였다.

또한 한 번 실패한 노드는 재방문하고 또 방문하는 경우를 막기 위해서 visited를 두었고, 재방문에도 실패해서 chk가 -1이 나올 경우 visited에 next가 없을 때에만 search에 다시 추가하도록 했다.

그리고 실패했다. 정확성 72.2점이 나왔다.

시도 2

def solution(info, edges):
    answer = [0]

    adj = [[] for _ in range(len(info))]

    for a, b in edges:
        adj[a].append(b)

    dfs(0, adj, info, 1, 0, answer, [])
    return answer[0]

def dfs(start, adj, info, sheep, wolves, answer, track):

    if wolves >= sheep:
        return -1
    answer[0] = max(answer[0], sheep)

    search = adj[start] + track
    visited = set()
    while search:
        next = search.pop()
        chk = dfs(next, adj, info, sheep + abs(info[next] - 1), wolves + info[next], answer, search)
        if chk == -1 and next not in search and next not in visited:
            search.append(next)
            visited.add(next)

    search = adj[start] + track
    visited = set()
    while search:
        next = search.pop(0)
        chk = dfs(next, adj, info, sheep + abs(info[next] - 1), wolves + info[next], answer, search)
        if chk == -1 and next not in search and next not in visited:
            search.append(next)
            visited.add(next)

질문하기에서 주운

입력값 [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [4, 9], [9, 10], [10, 11], [8, 12], [12, 13], [13, 14], [14, 15], [15, 16]]

기댓값 11

케이스에 대해서 그림을 그리면

이런 모양이 나와서 자식이 두 개인 노드에 대해서 왼쪽 먼저 탐색하는 경우와 오른쪽 먼저 탐색하는 경우 두 가지를 모두 찾아봐야했다. 하지만 set은 순서가 없어서 항상 같은 방향으로만 탐색이 되어서 list로 변경하고, 노드의 개수가 최대 17이기에 next in search를 매번 호출해도 부담이 없어서 해당 조건을 주었더니 통과할 수 있었다.

이렇게 생긴 윷놀이 판을 이동해서 최대 점수를 얻게하는 문제이다.

말 4개가 있고 10번의 턴이 있기 때문에 최대 4^10의 경우라서 완전탐색을 진행했다.

Python

시도 1 - 실패

nums = list(map(int, input().split()))

graph = dict()
blue = dict()

score = [
    0,
    2,
    4,
    6,
    8,
    10,
    13,
    16,
    19,
    25,
    12,
    14,
    16,
    18,
    20,
    22,
    24,
    22,
    24,
    26,
    28,
    30,
    32,
    34,
    36,
    38,
    26,
    27,
    28,
    30,
    35,
    40,
    0,
]

graph[0] = [1]
graph[1] = [2]
graph[2] = [3]
graph[3] = [4]
graph[4] = [5]
graph[5] = [10]
graph[6] = [7]
graph[7] = [8]
graph[8] = [9]
graph[9] = [29]
graph[10] = [11]
graph[11] = [12]
graph[12] = [13]
graph[13] = [14]
graph[14] = [17]
graph[15] = [16]
graph[16] = [9]
graph[17] = [18]
graph[18] = [19]
graph[19] = [20]
graph[20] = [21]
graph[21] = [22]
graph[22] = [23]
graph[23] = [24]
graph[24] = [25]
graph[25] = [31]
graph[26] = [9]
graph[27] = [26]
graph[28] = [27]
graph[29] = [30]
graph[30] = [31]
graph[31] = [32]

blue[5] = [6]
blue[14] = [15]
blue[21] = [28]

ans = 0

horses = [0, 0, 0, 0]


def move(next, count):
    while count > 0 and next != 32:
        next = graph[next][0]
        count -= 1
    return next


def backtracking(horses, idx, s):
    global ans

    if idx == 10:
        ans = max(ans, s)
        return

    for i in range(4):
        count = nums[idx]
        now = horses[i]

        if now == 32:
            continue

        next = move(now, count)

        if next not in horses or next == 32:
            horses[i] = next
            backtracking(horses, idx + 1, s + (score[next] if next != 32 else 0))
            horses[i] = now

        if now in blue:
            next = move(blue[now][0], count - 1)

            if next not in horses or next == 32:
                horses[i] = next
                backtracking(horses, idx + 1, s + (score[next] if next != 32 else 0))
                horses[i] = now


backtracking(horses, 0, 0)

print(ans)

사진처럼 번호를 부여하고, 그래프를 만든 후 백트래킹을 했다. 파란색 칸을 만나면 빨간길과 파란길 두 가지 다 탐색하도록 했다. 그리고 실패했다.

시도 2 - 실패

nums = list(map(int, input().split()))

# routes = [
#     [-1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0],
#     [10, 13, 16, 19, 25, 30, 35, 40, 0],
#     [20, 22, 24, 25, 30, 35, 40, 0],
#     [30, 28, 27, 26, 25, 30, 35, 40, 0],
# ]

routes = [
    [-1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0],
    [-1, 13, 16, 19, 25, 30, 35, 40, 0],
    [-1, 22, 24, 25, 30, 35, 40, 0],
    [-1, 28, 27, 26, 25, 30, 35, 40, 0],
]

blue = [5, 10, 15]


horse = [0, 0, 0, 0]
hr = [0, 0, 0, 0]
ans = 0


def backtracking(horse, idx, score):
    if idx == 10:
        global ans
        ans = max(ans, score)
        return

    for i in range(4):
        now = horse[i]
        route = routes[hr[i]]
        count = nums[idx]

        if route[now] == 0:
            continue
        next = min((now + count), len(route) - 1)

        chk = True
        for h in range(4):
            if i == h:
                continue
            if horse[h] == next and hr[i] == hr[h]:
                chk = False
                break
        if chk:
            horse[i] = next
            backtracking(horse, idx + 1, score + route[next])
            horse[i] = now

        if now in blue:
            original_hr = hr[i]
            r = blue.index(now) + 1
            hr[i] = r
            route = routes[hr[i]]

            chk = True
            for h in range(4):
                if i == h:
                    continue
                if horse[h] == next and hr[i] == hr[h]:
                    chk = False
                    break

            if chk:
                next = min((now + count), len(route) - 1)
                horse[i] = next
                backtracking(horse, idx + 1, score + route[next])
                horse[i] = now
            hr[i] = original_hr


backtracking(horse, 0, 0)
print(ans)

질문하기에 루트만 따로 추출해서 문제를 접근하길래 이 방식을 해보았다. 결과는 시도 1과 같았다.

시도 3

nums = list(map(int, input().split()))

graph = dict()
blue = dict()

score = [
    0,
    2,
    4,
    6,
    8,
    10,
    13,
    16,
    19,
    25,
    12,
    14,
    16,
    18,
    20,
    22,
    24,
    22,
    24,
    26,
    28,
    30,
    32,
    34,
    36,
    38,
    26,
    27,
    28,
    30,
    35,
    40,
    0,
]

graph[0] = [1]
graph[1] = [2]
graph[2] = [3]
graph[3] = [4]
graph[4] = [5]
graph[5] = [10, 6]
graph[6] = [7]
graph[7] = [8]
graph[8] = [9]
graph[9] = [29]
graph[10] = [11]
graph[11] = [12]
graph[12] = [13]
graph[13] = [14]
graph[14] = [17, 15]
graph[15] = [16]
graph[16] = [9]
graph[17] = [18]
graph[18] = [19]
graph[19] = [20]
graph[20] = [21]
graph[21] = [22, 28]
graph[22] = [23]
graph[23] = [24]
graph[24] = [25]
graph[25] = [31]
graph[26] = [9]
graph[27] = [26]
graph[28] = [27]
graph[29] = [30]
graph[30] = [31]
graph[31] = [32]
graph[32] = [32]

ans = 0

horses = [0, 0, 0, 0]


def move(next, count):
    while count > 0 and next != 32:
        next = graph[next][0]
        count -= 1
    return next


def backtracking(horses, idx, s):
    global ans

    if idx == 10:
        ans = max(ans, s)
        return

    for i in range(4):
        count = nums[idx]
        now = horses[i]

        next = graph[now][-1]
        next = move(next, count - 1)

        if next not in horses or next == 32:
            nhorse = horses[:]
            nhorse[i] = next
            backtracking(nhorse, idx + 1, s + score[next])


backtracking(horses, 0, 0)

print(ans)

문제를 제대로 안 읽어서 실패한 것이었다. 파란칸이면 파란길로만 이동해야하는 조건이 있었는데 그걸 놓쳤다.

파란 칸일 때는 파란길만 가게 설정했더니 통과할 수 있었다.

충분히 시간 안에 풀 수 있는 문제였는데 문제를 제대로 안 읽어서 실패했다. 막히면 문제를 제대로 다시 읽는 습관을 들여야겠다.