태야

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

<내 코드>

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 배열의 가장 마지막 요소를 출력하면 몇 번째만에 도착인지 알 수 있다.