DFS와 BFS (실버 2)

문제 이해가 매우 쉬운 문제 그냥 DFS, BFS를 구현하라는 것이다.

from sys import stdin
from collections import deque
from queue import Queue

n, link, start = map(int, stdin.readline().split())

graph = [[] * (n + 1) for _ in range(n + 1)]

# 그래프 만들기
for i in range(1,link+1):
    link1, link2 = map(int, stdin.readline().split())
    if link2 not in graph[link1]:
        graph[link1].append(link2)
    if link1 not in graph[link2]:
        graph[link2].append(link1)

graph = [sorted(i) for i in graph]


def DFS(graph, start):
    visited = [start]
    que = deque()

    # 초기화 #
    for i in graph[start]:
        que.append(i)
    
    while len(que) != 0:
        item = que.popleft()
        if item not in visited:
            visited.append(item)

        for i in graph[item][::-1]:
            if i not in visited:
                que.appendleft(i)
    result = " ".join(map(str, visited))
    print(result)

def BFS(graph, start):
    visited = [start]
    que = Queue()

    for i in graph[start]:
        que.put(i)
    
    while not que.empty():
        item = que.get()
        if item not in visited:
            visited.append(item)
            for i in graph[item]:
                if i not in visited:
                    que.put(i)
    result = " ".join(map(str, visited))
    print(result)

DFS(graph, start)
BFS(graph, start)

우선 주어진 입력을 활용해 그래프 관계도를 만든다. 이중 리스트를 활용했으며, 리스트안의 리스트는 각 인덱스와 연결된 인덱스를 담는다. 만약 2 5라면 2에도 5를 추가해주고, 5에도 2를 추가해준다.

DFS의 경우 planner로 deque를 사용했다. 큐에 1,2,3이 들어왔다면 1을 처리할 때 1이 처리될 때 들어오는 추가 데이터들을 2,3 보다 우선 처리해야하므로 데이터는 왼쪽에 추가해준다. [::-1]을 한 이유는 오름차순으로 정렬되어 있기에 거꾸로 넣어야 가장 왼쪽에 가장 작은 수가 들어오기 때문이다. 큐가 빈 큐가 될 때까지 내부 코드를 반복한다. 스택으로도 처리가 가능할 듯 하다. 스택은 하지만 라이브러리 제공이 없어서 deque로 빠르게 구현했다.

BFS의 경우 단순queue를 사용했다. 큐에 1,2,3이 들어오고 처리가 시작될 때 1이 처리될 때 발생하는 데이터들을 3 뒤에 계속 쌓아준다. 처리는 항상 왼쪽에서 꺼내는 get을 통해, 쌓는 것은 항상 오른쪽에 넣어준다.

미로 탐색 (실버 1)

최단거리를 구해야 한다. BFS로 구해야 한다. 그 이유는 BFS는 현재 노드에서 그 다음 단계 노드를 이후의 모든 단계보다 우선적으로 접근하기 때문이다. 현재노드 그 다음 단계 노드를 업데이트할 때 거리도 같이 업데이트하면 된다.

직접 주어진 입력의 예시를 손으로 바꿔보면 BFS임을 바로 파악 가능하다.

from sys import stdin
from queue import Queue
row_, col_ = map(int, stdin.readline().split())

my_map = [[] for _ in range(row_)]
my_visited = [[0]*col_ for _ in range(row_)]

for i in range(row_):
    m_row = str(stdin.readline().strip())
    for j in m_row:
        num = int(j)
        my_map[i].append(num)
        
def solution(my_map, my_visited):
    row = 0
    col = 0
    planner = Queue()
    # 초기화
    planner.put((row, col))
    
    while not planner.empty():
        row, col = planner.get()
        if 0 <= row + 1 < row_:
            if my_map[row+1][col] > 0 and my_visited[row+1][col] < 1:
                my_visited[row+1][col] = my_visited[row][col] + 1
                planner.put((row+1, col))
                
        if 0 <= row - 1 < row_:
            if my_map[row-1][col] > 0 and my_visited[row-1][col] < 1:
                my_visited[row-1][col] = my_visited[row][col] + 1
                planner.put((row-1, col))
            
        if 0 <= col + 1 < col_:
            if my_map[row][col+1] > 0 and my_visited[row][col+1] < 1:
                my_visited[row][col+1] = my_visited[row][col] + 1
                planner.put((row, col+1))
                
        if 0 <= col - 1 < row_:
            if my_map[row][col-1] > 0 and my_visited[row][col-1] < 1:
                my_visited[row][col-1] = my_visited[row][col] + 1
                planner.put((row, col-1))  
                
    print(my_visited[row_ - 1][col_ - 1] + 1)

solution(my_map, my_visited)

BFS이므로 queue를 사용했고, 접근된 노드에서 다음 단계 노드를 가는 경우의 수는 4가지이다. 하지만 인덱스가 음수이거나, max_index를 넘어갈 경우에는 접근하지 말아야 하므로 if문으로 1차적으로 제한하고, 2차적으로 그 곳이 1이어야 하며 방문한 적이 없어야 한다. 이렇게 queue의 길이가 0이 될 때까지 반복한다. my_visited를 방문확인용 + 거리확인용으로 같이 썼다.

전쟁 - 전투 (실버1)

재밌는 문제이다. 연결된 노드들끼리 power를 구하는 문제이다. 연결되어있는 집단이 되면 그 집단 내의 사람수의 제곱의 힘을 가진다. BFS든 DFS든 상관 없다.

from sys import stdin
from queue import Queue
col, row = map(int, stdin.readline().split())

field = [[] for _ in range(row)]
field_visited = [[0]*col for _ in range(row)]

for i in range(row):
    field[i] = list(str(stdin.readline()))
    
def linked(start_row, start_col, field_visited, field):
    can_go_que = Queue()
    color = field[start_row][start_col]
    field_visited_set = field_visited.copy()
    
    # __init__
    row = start_row
    col = start_col
    can_go_que.put((row, col))
    field_visited_set[row][col] = 1
    count = 1
    
    while can_go_que.qsize() != 0:
        row, col = can_go_que.get()
        
        if 0 <= row - 1 < (len(field)): 
            if field[row-1][col] == color and field_visited_set[row-1][col] == 0:
                can_go_que.put((row-1, col))
                field_visited_set[row-1][col] = 1
                count += 1
        if 0 <= row + 1 < (len(field)): 
            if field[row+1][col] == color and field_visited_set[row+1][col] == 0:
                can_go_que.put((row+1, col))
                field_visited_set[row+1][col] = 1
                count += 1
        if 0 <= (col-1) < (len(field[0])): 
            if field[row][col-1] == color and field_visited_set[row][col-1] == 0:
                can_go_que.put((row, col-1))
                field_visited_set[row][col-1] = 1
                count += 1
        if 0 <= (col+1) < (len(field[0])): 
            if field[row][col+1] == color and field_visited_set[row][col+1] == 0:
                can_go_que.put((row, col+1))
                field_visited_set[row][col+1] = 1
                count += 1


	if count > 1:
    	count = count ** 2
    
    return field_visited_set, count, color
        
power_map = {"W": 0, "B": 0}
for i in range(row):
    for j in range(col):
        if field_visited[i][j] == 0:
            field_visited, count, color = linked(i, j, field_visited, field)
            power_map[color] += count
            count = 0

            
print(power_map["W"], power_map["B"])

미로 탐색과 문제가 비슷하다. 미로 탐색의 경우는 탐색될 곳이 0혹은1인 경우이고, 0은 방문안해도 된다. 그리고 1은 모두 연결되어 있다. 하지만 전쟁 - 전투는 탐색될 곳이 W or B이고 각각의 W,B는 연결이 끊겨 있는 경우도 있다. 그렇기에 모든 행열요소를 조회해야한다. 하지만 이미 visited되어 있을 경우 함수를 돌리지 않고 지나가면 함수 실행은 행렬의 전체 요소 개수만큼 되긴 힘들다.

// 점심시간, 퇴근 후 시간 2시간 씩은 쓰고있다. 동기가 평균 티어가 골드1이라는데 한 달안에 따라잡아야지 근데 티어 시스템이 좀 이상하다. 최근 푼 문제 100문제를 기준으로 하면, 한창 플래티넘 풀다가 심심해서 브론즈 풀면 내 티어는 망하는건데... 또 이상한건 생각보다 그 티어에 맞지 않아보이는 문제가 많아보인다. 여기도 브실골플 하나로 묶이나 싶다.