수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/2178

문제 이해

- 기본적인 bfs 문제이다.

- 왼쪽 끝에서 시작해 오른쪽 아래 끝까지 이동할 때 지나는 최소의 칸 수를 구하면 된다. 

풀이 로직

- 과정은 기본 bfs로 진행하면 된다. 

- 주어지는 행렬(matirx)과 방문여부를 확인하는 행렬(visit)을 따로 두어도 되지만, 이 때는 주어진 행렬로 탐색하면서 이전 노드의 값 + 1을 하면서 matrix가 visit 역할도 할 수 있게 했다. 

- 주의해야할 점은 행렬의 원소들 사이에 띄어쓰기가 없다는 것이다. 그래서 map(int, input().split())이 아닌 map(int, input())으로 입력해야한다. 

- 이동하면서 matrix[-1][-1]에 도착하지 못할 수도 있을거라 생각했는데, 아래 풀이가 정답인 걸 보면 일단 출발하면 목적지에 도착하는 방식인 것 같다. 

- 그래서 matrix[-1][-1]에 무조건 도착하므로 해당 행렬값을 출력하면 된다. 

정답 풀이

n, m = map(int, input().split())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, input())))
    
queue = [[0, 0]]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
while queue:
    x, y = queue.pop(0)
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if matrix[nx][ny] == 1:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])
                
print(matrix[-1][-1])

- 문제 : https://www.acmicpc.net/problem/1012

문제 이해

- 2차 행렬에서 1로만 이루어진 영역의 개수를 세는 문제다. 

- 영역의 개수를 세기 위해 bfs를 이용하면 된다.

- 탐색을 위한 조건으로는 (방문하지 않은 노드) + (기존 행렬 값 == 1)이어야 한다. 

- 그 외에는 일반 bfs 함수로 진행하면 된다. 

정답 풀이 

import sys
input = sys.stdin.readline

def bfs(x, y, visit):
    queue = [[x, y]]
    visit[x][y] = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if not visit[nx][ny] and matrix[nx][ny] == 1:
                    visit[nx][ny] = 1
                    queue.append([nx, ny])
        
    
for _ in range(int(input())):
    m, n, k = map(int, input().split())
    matrix = [[0] * n for _ in range(m)]
    for _ in range(k):
        a, b = map(int, input().split())
        matrix[a][b] = 1
        
    visit = [[0] * n for _ in range(m)]  
    answer = 0 
    for i in range(m):
        for j in range(n):
            if not visit[i][j] and matrix[i][j] == 1:
                answer += 1
                bfs(i, j, visit)
                
    print(answer)

- 문제 : https://www.acmicpc.net/problem/1260

보기에는 간단한 것 같은데 생각을 좀 해야하는 문제였다. 

문제 이해

- dfs, bfs 함수를 각각 구현해야 하는 문제이다.

- 각 함수에서 지나는 노드들을 dfs, bfs 별로 순차적으로 출력해야한다.

- 연결된 노드 중에서 작은 값 순서대로 진행해야 한다고 나와있어 각 graph 원소마다 sort()를 해줘야 한다. 

- 지나는 노드들은 배열에 저장하는데 함수별로 arr_dfs, arr_bfs를 전역변수로 지정해 함수가 끝나도 배열이 유지될수 있게 한다. 

- 배열은 [a, b, c] 형태인데 정답은 a b c 형태로 출력해야하므로 마지막에 for문으로 정답에 맞는 형식으로 출력한다. 

- 각 함수마다 사용하는 visit가 다르므로 dfs, bfs 별로 visit를 따로 설정해줘야 한다. 

정답 풀이 

n, m, v = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()
    
def dfs(node, arr, visit):
    visit[node] = 1
    for each in graph[node]:
        if not visit[each]:
            arr.append(each)
            dfs(each, arr, visit)


def bfs(node, arr, visit):
    queue = [node]
    visit[node] = 1
    
    while queue:
        x = queue.pop(0)
        for each in graph[x]:
            if not visit[each]:
                visit[each] = 1
                arr.append(each)
                queue.append(each)

arr_dfs = [v]
visit = [0] * (n + 1)
dfs(v, arr_dfs, visit)

arr_bfs = [v]
visit = [0] * (n + 1)
bfs(v, arr_bfs, visit)

for i in range(len(arr_dfs)):
    print(arr_dfs[i], end = ' ')
print()
for i in range(len(arr_bfs)):
    print(arr_bfs[i], end = ' ')

- 문제 : https://www.acmicpc.net/problem/2644

문제 이해

그래프를 만든 뒤 두 노드 사이에 몇 개의 간선이 있는지 확인하는 문제라고 이해했다. 

간선 개수를 확인하기 위해 bfs를 이용해야 한다. 

(부모 -> 자식) 관계도 있지만 (자식 -> 부모) 관계도 있기 때문에 양방향 간선으로 graph에 저장해야한다. 

풀이 로직

- 찾아야하는 두 노드를 first, second라고 한 뒤 양방향 간선 정보를 graph에 저장한다.

- 탐색하는 노드가 찾고자 하는 second 노드라면 answer를 level로 업데이트 해준 뒤 break 한다.

- first노드 부터 그래프 탐색을 시작하는데, visit[first] = 1 을 해준다.

- queue는 [노드, first로부터의 간선 개수]로 설정했다. 

- 연결되었지만 방문하지 않은 노드를 중심으로 탐색한다. 탐색하면서 간선을 하나씩 지나가므로 level + 1 해준다. 

- if 문에서 break 해서 나온 answer라면 -1이 아닌 양수를 출력하고, 그렇지 않다면 -1을 출력한다. 

정답 풀이 

n = int(input())
first, second = map(int, input().split()) 
m = int(input())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a) # 여기 추가 안 해서 틀림

queue = [[first, 0]]
visit = [0] * (n + 1)
visit[first] = 1
answer = -1
while queue:
    person, level = queue.pop(0)
    
    if person == second:
        answer = level
        break
    
    for each in graph[person]:
        if not visit[each]:
            visit[each] = 1
            queue.append([each, level + 1])

print(answer)