태야

<내 코드>

import sys
sys.setrecursionlimit(10000)

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


def dfs(x, y, h):

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

        if(0 <= nx < N) and (0 <= ny < N):
            if arr[nx][ny] > h and done[nx][ny] == 0:
                done[nx][ny] = 1
                dfs(nx, ny, h)


N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
ans = 0

for k in range(max(map(max, arr))):  # 주어진 배열에서 가장 큰값만큼 반복
    # 매번 초기화
    cnt = 0
    done = [[0]*N for _ in range(N)]

    # 입력 받은 arr배열 탐색
    for i in range(N):
        for j in range(N):
            if arr[i][j] > k and done[i][j] == 0:
                done[i][j] = 1
                cnt += 1
                dfs(i, j, k)

    ans = max(ans, cnt)


print(ans)

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

이 문제에서 중요한 것이 물의 높이 1부터 ~ 가장 높은 높이까지 반복하며, 안전 영역의 최댓값을 구하는 거다. 

max(map(max, arr)) 구문을 통해서 입력 배열에서 가장 큰 값(이 예에서는 9)을 구할 수 있다. 그리고 매 dfs 탐색이 끝나면 이전 안전 영역 개수(ans)와 현재 탐색의 안전 영역 개수(cnt) 중 큰 값을 비교해 담는다.

<내 코드>

- DFS

import sys
sys.setrecursionlimit(10000)


def dfs(x, y, type):

    done.append((x, y))

    # 4방향 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if(0 <= nx < N) and (0 <= ny < N) and ((nx, ny) not in done):
            # 정상인
            if type == 0 and colors[nx][ny] == colors[x][y]:
                dfs(nx, ny, 0)
            # 적록색맹
            elif type == 1 and colors[nx][ny] == colors[x][y]:
                dfs(nx, ny, 1)


N = int(input())
colors = [list(input()) for _ in range(N)]

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

# 정상인인 경우
done = []
cnt_1 = 0

for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            dfs(i, j, 0)
            cnt_1 += 1


# 적록색맹인 경우
for i in range(N):
    for j in range(N):
        if colors[i][j] == 'G':
            colors[i][j] = 'R'

done = []
cnt_2 = 0
for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            dfs(i, j, 1)
            cnt_2 += 1

print(cnt_1, cnt_2)

DFS로 풀 때 런타임 에러 방지하기 위해 sys.setrecursionlimit(10000) 설정해준다. 그리고 type 값에 따라 정상인과 색약의 상태를 구분해 탐색한다. 시간을 조금 더 줄여보는 방법을 생각해봐야겠다.

- BFS

from collections import deque


def bfs(x, y):
    queue.append((x, y))
    done.append((x, y))
    
    while queue:
        curr = queue.popleft()

        for i in range(4):
            nx = curr[0] + dx[i]
            ny = curr[1] + dy[i]

            if (0 <= nx < N) and (0 <= ny < N) and ((nx, ny) not in done):
                if colors[nx][ny] == colors[curr[0]][curr[1]]:
                    queue.append((nx, ny))
                    done.append((nx, ny))


N = int(input())
colors = [list(input()) for _ in range(N)]

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

# 정상인인 경우
queue = deque()
done = []
cnt_1 = 0

for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_1 += 1


# 적록색맹인 경우
for i in range(N):
    for j in range(N):
        if colors[i][j] == 'G':
            colors[i][j] = 'R'

queue = deque()
done = []
cnt_2 = 0
for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_2 += 1

print(cnt_1, cnt_2)

<내 코드>

import sys
sys.setrecursionlimit(10000) 


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

    global ans
    ans = max(ans, cnt)

    for i in range(4):
        nx = now[0] + dx[i]
        ny = now[1] + dy[i]

        if(0 <= nx < R) and (0 <= ny < C):
            if(done[strings[nx][ny]] == 0):
                done[strings[nx][ny]] = 1
                # print(done)
                dfs(nx, ny, cnt+1)
                done[strings[nx][ny]] = 0  #백트래킹


R, C = map(int, input().split())
strings = [list(map(lambda x: ord(x)-65, input())) for _ in range(R)] # 아스키 코드로 바꿔줌
done = [0]*26   # 알파벳 26개만큼 배열설정
done[strings[0][0]] = 1

ans = 1

dfs(0, 0, ans)
print(ans)

계속해서 시간 초과가 나서 실패하고, 이 코드로 겨우 통과했다. 알고리즘은 계속해서 맞았지만 재귀를 활용하다 보니 시간 초과가 많이 났다. 백트래킹의 기본 동작원리를 이해할 수 있는 문제였다.

<내 코드>

T = int(input())
for _ in range(T):
    strings = list(input())

    if strings[0] == 'O':
        strings[0] = 1
    else:
        strings[0] = 0

    for i in range(1, len(strings)):
        if strings[i-1] != 'O' and strings[i] == 'O':
            strings[i] = strings[i-1] + 1
        else:
            strings[i] = 0
    print(sum(strings))