4/2 Coding Test

✅ 문제 풀이 - (Graph 탐색)

🎈 2644 촌수계산

부모와 자식 사이를 1촌 관계로 두고 여러 사람들에 대해 부모 자식 가 관계가 주어질 때 두 사람의 촌수를 계산하는 문제
입출력은 다음과 같다

• 입력 : 첫 줄에는 사람 수 n , 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두사람의 번호, 셋째 줄에는 부모 자식 관계 수 m, 이후 m줄만큼 x,y가 주어지는데 x는 y의 부모 번호를 의미한다.
• 둘째줄에서 주어진 두사람의 번호로 촌수를 구하고, 관계가 전혀없는 경우 -1을 출력한다.

# dfs
import sys
input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
m = int(input())
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
def dfs(node):
    for i in graph[node]:
        if not visited[i]:
            visited[i] = visited[node] + 1
            dfs(i)
dfs(a)
if visited[b] > 0:
    print(visited[b])
else:
    print(-1)

# bfs
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if not visited[i]:
                visited[i] = visited[node] + 1
                queue.append(i)
bfs(a)
if visited[b] > 0:
    print(visited[b])
else:
    print(-1)

< 풀이 과정 >
DFS, BFS로 각각 풀이하였다.
graph로 (n+1) 길이만큼 만들어주고 visited로 (n+1)만큼 리스트를 생성해 해당 노드를 방문했는지 확인한다.
bfs, dfs 모두 노드를 입력받아 해당 노드를 기준으로 다음 노드를 방문하지 않은 경우 visited를 + 1을 해주면서 최종적으로 촌수를 계산해준다.

🎈 7562 나이트의 이동

체스판 위에 나이트가 이동하려는 칸이 주어지는데, 해당 칸으로 몇번 움직여야 이동할 수 있는지 구하는 문제
입출력은 다음과 같다

• 입력 : 첫 줄에 테스트 케이스 개수가 주어지고 각 테케는 세줄로 구성됐다. 첫 줄은 체스판 한 변의 길이, 둘째줄, 셋째줄에는 출발지와 도착지가 주어진다.

import sys
input = sys.stdin.readline
from collections import deque

dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]
def bfs():
    queue = deque()
    queue.append((sx, sy))
    while queue:
        x, y = queue.popleft()
        if x == ex and y == ey:
            return graph[x][y]
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < l and 0 <= ny < l and not graph[nx][ny]:
                queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1
t = int(input())
for _ in range(t):
    l = int(input())
    graph = [[0] * l for _ in range(l)]
    visited = [[0] * l for _ in range(l)]
    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())
    print(bfs())

< 풀이 과정 >
graph를 만들어 시작점을 큐에 넣어 다음 위치를 방문하면 + 1하는 방식으로 계산해 몇 번 이동하는지 정하였고, 도착지인 ex, ey에 닿으면 graph[x][y]를 리턴한다.

🎈 1389 케빈 베이컨의 6단계 법칙

해당 법칙에 의하면 지구 상 모든 사람들은 6단계를 거치면 서로 아는사람으로 연결될 수 있다. 첫 줄에는 유저 수 n과 친구 관계 수 m이 주어지고 m줄 만큼 친구 관계 a, b가 주어진다. 최종적으로 케빈 베이컨 수가 가장 작은 사람의 번호를 출력하는 문제
(케빈 베이컨 수란, a단계에서 a 제외한 나머지 b들까지의 이동되는 단계 수의 합을 의미)

import sys
input = sys.stdin.readline
from collections import deque

n, m = 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)
def bfs(start):
    number = [0] * (n+1)
    queue = deque()
    queue.append(start)
    visited[start] = 1
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                queue.append(i)
                visited[i] = 1
                number[i] = number[x] + 1
    return sum(number)
answer = []
for i in range(1, n+1):
    visited = [0] * (n+1)
    answer.append(bfs(i))
print(answer.index(min(answer)) + 1)

< 풀이 과정 >
graph를 생성한 후 입력받는 a, b를 이용하여 양방향 그래프로 생성해준다.
bfs함수를 만들어 시작노드 기준 도착 노드까지의 단계를 number로 저장하기 위해 number를 만들고, queue가 빌때까지 현위치와 연결되어있는 다음 위치에 한해 방문하지 않은 곳이면, 단계 + 1, 큐에 다음 위치 넣는 과정을 반복해준다.

최종적으로 for문으로 1~n까지 n번 반복하며 visited로 매번 리셋해주어 answer에 bfs 결과를 넣어준다. answer는 결국 시작지 > 도착지로의 모든 단계의 합이 되고 최소 단계의 인덱스 + 1을 결과로 출력해준다.

✅ 문제 풀이 - Brute Force

🎈 1107 리모컨

현재 채널이 100이고 주어진 리모컨의 버튼은 0~9, -, + 로 구성되어 있다.
이동하려는 채널 n과 고장난 버튼 수 m, m개의 고장난 버튼이 주어질때 채널 n으로 이동하기 위해 몇번 버튼을 눌러야 하는지 출력하는 문제

import sys
input = sys.stdin.readline

# 가고자하는 채널 번호
n = int(input())
# 고장난 번호, 번호 버튼 
m = int(input())
broken = list(map(int, input().split()))
# 초기값 +, - 2가지 경우로 이동만 하는 경우
answer = abs(100-n)
# 완전 탐색 진행 (주어진 범위 내 모든 숫자에 대해)
for number in range(10**6 + 1):
	# 문자 처리 하여 인덱스 j로 부여
    number = str(number)
    for j in range(len(number)):
    	# 숫자 내 고장난 버튼 있으면 중단
        if int(number[j]) in broken:
            break
        # 숫자 끝 인덱스까지 고장 버튼 없으면 min(기존 답, 해당 번호 - 타겟 + 버튼 누른 횟수)
        elif j == len(number) - 1:
            answer = min(answer, abs(int(number) - n) + len(number))
print(answer)

< 풀이 과정 >
고장난 버튼이 있으면 해당 숫자 횟수를 중단하고 다음 번호로 넘어가는 것이 핵심인 문제
주어진 n의범위가 500000인데 작은수에서 큰수로의 이동 반대의 경우를 체크하여 10**6으로 지정한 후, number를 문자로 처리하여 j로 인덱스를 부여해준다.
만일 숫자 내 고장난 버튼이 있으면 break해주고, 고장난 버튼이 해당 숫자에 없는 건에 한해 answer를 min(최솟값, 해당번호-타겟 + 버튼 누른 횟수)로 값을 갱신해나간다.