태야

<내 코드>

from collections import deque


def bfs(s):
    q = deque()
    visited = [0 for _ in range(n+1)]

    q.append(s)
    visited[s] = 1

    while q:
        x = q.popleft()

        for i in tree[x]:
            if visited[i] == 0:
                visited[i] = 1
                result[i] = result[x] + 1
                q.append(i)


n = int(input())
a, b = map(int, input().split())
m = int(input())
tree = [[] for _ in range(n+1)]
result = [0 for _ in range(n+1)]

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

bfs(a)
if result[b] != 0:
    print(result[b])
else:
    print(-1)

BFS로 그래프를 탐색하며 현재 탐색하는 노드와 연결된 노드에 현재 노드 값의 +1을 한다. 즉, 연결된 노드를 이동하는 것을 의미한다.

이런 식으로 모든 노드들을 탐색을 마치면 찾고자 하는 노드의 인덱스의 값을 출력해주면 된다.

<내 코드>

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

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인 좌표값들을 동시에 탐색하도록 하는 것이다. 

<내 코드>

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