태야

<내 코드>

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

<내 코드>

import sys
sys.setrecursionlimit(10000)


def dfs(v):

    done[v] = v

    for i in gragh[v]:
        if (i != 0) and (i not in done):
            dfs(i)


vertex, edge = map(int, input().split())
gragh = [[0]*(vertex + 1) for _ in range(vertex + 1)]
done = [0]*(vertex + 1)
cnt = 0

for _ in range(edge):
    x, y = map(int, input().split())
    gragh[x][y] = y
    gragh[y][x] = x

for w in range(1, vertex+1):
    if w not in done:
        dfs(w)
        cnt += 1

print(cnt)

처음에 런타임 에러가 계속 나서 뭐가 문제인지 몰랐다.. 검색 결과 python은 재귀 제한이 걸려있기 때문에 재귀 허용치가 넘어가면 런타임 에러를 일으킨다. 때문에 sys.setrecursionlimit(10000)처럼 작성해야 한다는 것을 알게 됐다.

sys.setrecursionlimit() 메서드는 Python 인터프리터 스택의 최대 깊이를 필요한 제한으로 설정하는 데 사용된다. 이 제한은 모든 프로그램이 무한 재귀에 들어가는 것을 방지한다. 제한이 너무 높으면 충돌이 발생해 주의가 필요하다.

<내 코드>

N = int(input())
P = int(input())
# 인덱스 번호 맞추기 위해 한 줄 추가
graph = [[0]*(N+1) for _ in range(N+1)]
done = []

for _ in range(P):
    x, y = map(int, input().split())
    graph[x][y], graph[y][x] = 1, 1


def dfs(v):
    done.append(v)
    for k in range(1, N+1):  # 1 ~ n번까지
        if (k not in done) and (graph[v][k] == 1):
            dfs(k)

    return (len(done) - 1)  # 1번을 제외한 컴퓨터 수


print(dfs(1))

문제 자체는 DFS를 구현한다면 어렵지 않았다. 아직은 DFS를 자유롭게 구현하는게 힘들다...이 문제에서 인접행렬 방식을 이용해 DFS를 구현했다.

<내 코드>

N, M = map(int, input().split())
maze = [list(input()) for _ in range(N)]  # List[str]
# 방문 경로
done = [[0]*M for _ in range(N)]

# 좌,우,상,하 탐색을 위한 설정
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# BFS 그래프 탐색
def bfs(x, y):

    done[0][0] = 1  # 시작점
    queue = [(0, 0)]  # 큐 사용

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

            if (0 <= nx < N) and (0 <= ny < M):
                if done[nx][ny] == 0 and maze[nx][ny] == '1':
                    done[nx][ny] = done[now[0]][now[1]] + 1
                    queue.append((nx, ny))
    return done[-1][-1]

print(bfs(0, 0))

처음 풀어보는 BFS 문제였는데.. 이해하는데 꽤나 어려웠다. 계속 반복적으로 생각하고 익혀야겠다.

1. 방문한 경로를 저장하기 위해 done 배열을 만든다.

2. 길을 찾아나갈 노드를 queue에 담아준다.

3. 좌표가 경로를 벗어나지 않는다면 '방문 여부 확인', '길이 맞는지' 확인한다.

4. 상,하,좌,우로 확인해 연결된 좌표를 확인한다.

5. 조건에 맞다면 방문 여부 수정 후, 큐에 넣어 다음 차례에 추가한다.

6. 방문여부 수정 때, 몇 번째 방문인지 현재 좌표의 방문 값에 +1을 더해준다.

7. done 배열의 가장 마지막 요소를 출력하면 몇 번째만에 도착인지 알 수 있다.

<내 코드>

def dfs(v):
    done.append(v)  # 방문한 노드 추가
    # print(done)
    # 해당 행(노드) 탐색(1행 ~ n행)
    for i in range(1, n+1):
        if (i not in done) and (matrix[v][i] == 1):
            dfs(i)

    return done


def bfs(start):
    queue = [start]
    done = [start]

    while queue:
        v = queue.pop(0)
        for i in range(1, n+1):
            if (i not in done) and (matrix[v][i] == 1):
                queue.append(i)
                done.append(i)

    return done


n, m, v = map(int, input().split())
done = []
matrix = [[0]*(n + 1) for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())
    matrix[x][y] = 1
    matrix[y][x] = 1

print(*dfs(v))
print(*bfs(v))

그래프를 표현하기 위해 여기서는 '인접 행렬' 방식으로 구현했다. DFS(깊이 우선 탐색)은 주로 스택과 재귀를 통해 구현하고 BFS(너비 우선 탐색)은 큐로 구현을 많이 한다.

<내 코드>

N, M = map(int, input().split())
cnt_block = 1


if N == 1:
    cnt_block = 1
elif N == 2:
    if (M >= 7):
        cnt_block = 4
    else:
        cnt_block = (M+1) // 2

elif N >= 3:
    if(M >= 7):
        cnt_block = (M - 2)
    elif(M >= 4):
        cnt_block = 4
    else:
        cnt_block = M

print(cnt_block)

경우 별로 따져줘야 할 조건이 까다로웠다... 문제 자체는 어렵지 않으나 경우 별로 조건을 잘 못하면 머리가 복잡해지는 문제다..

<내 코드>

N = int(input())
H = list(map(int, input().split()))
result = [0] * N

for i in range(N):
    cnt_zero = 0

    for j in range(N):
        if cnt_zero == H[i] and result[j] == 0:
            result[j] = i + 1  # 수 1 ~ N
            break
        elif(result[j] == 0):
            cnt_zero += 1

print(*result)

입력 값으로 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. 그리고 줄을 선 순서대로 키를 출력하면 된다. 

# result
# 입력: [2, 1, 1, 0]
[0, 0, 1, 0]
[0, 2, 1, 0]
[0, 2, 1, 3]
[4, 2, 1, 3]

차례대로 각자 왼쪽에 큰 사람이 몇 명인지를 0의 개수로 판단해서 자리에 넣어준다. 예를 들어 왼쪽에 2명이 있다 하면 결과값 배열에 [0, 0, 현재,...] 즉, 자신보다 큰 2명의 자리를 비워두고 자리에 들어가면 된다. 그렇게 되면 다음 사람은 앞전보다 큰 사람이기 때문에 앞사람 위치는 무시하고 자신보다 큰 사람 수와 0의 수만 같으면 그 자리에 들어가면 된다.