태야

<내 코드>

import sys
sys.setrecursionlimit(10000)


def dfs(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # 상,하,좌,우 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
    
        if (0 <= nx < N) and (0 <= ny < M):
            if matrix[nx][ny] == 1:
                matrix[nx][ny] = -1
                dfs(nx, ny)


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    matrix = [[0]*M for _ in range(N)]
    cnt = 0

    # 행렬 생성
    for _ in range(K):
        m, n = map(int, input().split())
        matrix[n][m] = 1

    for i in range(N):  # 행 (바깥 리스트)
        for j in range(M):  # 열 (내부 리스트)
            if matrix[i][j] > 0:
                dfs(i, j)
                cnt += 1

    print(cnt)

런타임 에러를 방지하기 위해 sys.setrecursionlimit(10000)를 사용했다. 

1. 현재 위치에서 상하좌우 확인한다.

2. 행렬 범위를 넘지 않고 조건을 만족한다면 지나온 값을 -1로 바꾸고 계속 연결된 지점을 탐색해 나간다.

3. 탐색을 마치면 카운트 값을 1 올려주고, 다른 요소들을 탐색한다.

4. 모든 연결된 부분들을 탐색을 마치면, 부분들이 몇 개인지 출력한다.

<내 코드>

n = int(input())
costs = [0 for _ in range(n+1)]
for i in range(1, n+1):
    costs[i] = list(map(int, input().split()))

for i in range(2, n+1):
    costs[i][0] = costs[i][0] + min(costs[i-1][1], costs[i-1][2])
    costs[i][1] = costs[i][1] + min(costs[i-1][0], costs[i-1][2])
    costs[i][2] = costs[i][2] + min(costs[i-1][0], costs[i-1][1])
   
print(min(costs[n][0], costs[n][1], costs[n][2]))

처음에 생각했을 때는 맨 처음 요소에서 최솟값을 구하면 최소가 되는 줄 알았는데, 그게 아니고 어떤 값을 선택했을 때 최소가 될지는 다 따져줘야 하는 문제였다. 다른 사람의 풀이를 참고하기 전까지는 쓸데없이 어렵게 풀고 헤맸다...

1. 첫 요소는 고정이므로 인덱스를 2번째부터 돌리면 된다. 

2. 현재 인덱스 요소의 값과 앞 요소에서 같은 색을 제외한 2가지 중에 최소를 더해준다.

3. 같은 방식으로 마지막까지 3가지 색에 대해 계산을 한다.

4. 마지막 요소의 3가지 값 중 최솟값을 선택하면 최소 비용값을 구할 수 있다.