태야

<내 코드>

- 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))

www.acmicpc.net/problem/2667

<내 코드>

from collections import deque


def bfs(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    cnt = 0
    queue = deque()

    queue.append((x, y))
    maps[x][y] = '0'
    done.append((x, y))

    while queue:
        now = queue.popleft()
        cnt += 1

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

            if(0 <= nx < N) and (0 <= ny < N):
                if maps[nx][ny] == '1' and ((nx, ny) not in done):
                    maps[nx][ny] = '0'
                    queue.append((nx, ny))
                    done.append((nx, ny))
    return cnt


N = int(input())
maps = [list(input()) for _ in range(N)]
done = []
total = 0
result = []


for i in range(N):
    for j in range(N):
        if maps[i][j] == '1':
            result.append(bfs(i, j))
            total += 1

result.sort()
print(total)
for i in range(total):
    print(result[i])

크게 어려움 없이 BFS 알고리즘만 구현하면 쉽게 풀리는 문제였다. 각 BFS마다 total과 cnt 값을 올려줘 총 몇 번의 BFS 탐색을 했고, 각 탐색 중 몇 번의 인접한 요소들을 찾아냈는지 표시했다. 그리고 그 값들을 출력해주면 끝이다.

<내 코드>

from collections import deque


def bfs():
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:

        now = queue.popleft()

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

            if(0 <= nx < N) and (0 <= ny < M):
                if tomato[nx][ny] == 0:
                    tomato[nx][ny] = tomato[now[0]][now[1]] + 1 # 현재 요소 값에서 +1
                    queue.append((nx, ny))


M, N = map(int, input().split())
queue = deque()
tomato = []

# 토마토 상자 배열
for _ in range(N):
    tomato.append(list(map(int, input().split())))

# 값이 1인 요소들을 큐에 다 담기(동시 진행을 위한)
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            queue.append((i, j))

# 탐색 시작
bfs()

ans = 0
for i in range(N):
    for j in range(M):
        if ans < tomato[i][j]:
            ans = tomato[i][j]
        if tomato[i][j] == 0:
            print(-1)
            exit()
        ans = max(ans, 1) # 1과 배열의 최대값과 비교
print(ans - 1)

기존 BFS 문제를 풀던 거보다 조금 더 복잡한 문제였다. 이번 문제는 BFS 탐색 안에서 큐에 값을 넣고 또 탐색 전에 미리 큐에 좌표를 넣어주는 문제였다. 그렇게 해서 값이 1인 좌표값들을 동시에 탐색하도록 하는 것이다. 

<내 코드>

from collections import deque


def bfs(x, y):
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1),
                 (1, 1), (1, -1), (-1, 1), (-1, -1)]

    queue = deque() #탐색을 하려는 좌표를 담는다.
    queue.append((x, y))

    maps[x][y] = 0

    while queue:
        now = queue.popleft()

        for i in range(8): #상하좌우 대각선까지 탐색
            nx = now[0] + direction[i][0]
            ny = now[1] + direction[i][1]

            if(0 <= nx < h) and (0 <= ny < w):
                if maps[nx][ny] == 1:
                    maps[nx][ny] = 0
                    queue.append((nx, ny))


while True:

    w, h = map(int, input().split())
    maps = []
    cnt = 0

    if w == 0 and h == 0:
        break

    for _ in range(h):
        tmp = list(map(int, input().split()))
        maps.append(tmp)

    for i in range(h):
        for j in range(w):
            if maps[i][j] != 0:
                cnt += 1
                bfs(i, j)

    print(cnt)

1. w, h, 지도를 입력받는다.

2. 매 입력마다 BFS 탐색을 마치면 cnt를 +1 해준다.

3. BFS를 상하좌우 그리고 대각선까지 여덟 방향을 다 탐색한다.

4. 탐색 중 지도에서 1인 값을 0으로 바꾸고 큐에 좌표를 넣고 탐색을 반복한다.

<내 코드>

from collections import deque


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

    queue = deque()
    queue.append((x, y))

    graph[x][y] = 1

    while queue:
        now = queue.popleft()

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

            if(0 <= nx < M) and (0 <= ny < N):
                if graph[nx][ny] == 0:
                    graph[nx][ny] = 1
                    queue.append((nx, ny))
                    cnt += 1
    return cnt


M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]
result = []
total = 0

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    # (x1, y1) ~ (x2, y2) 사각형 범위 1로
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1


for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            total += 1
            result.append(bfs(i, j))

result.sort()
print(total)
print(*result)

<내 코드>

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. 모든 연결된 부분들을 탐색을 마치면, 부분들이 몇 개인지 출력한다.