2/20 Coding Test

✅ 문제풀이

🎈 4963 섬의 개수

테스트 케이스 첫 줄에는 지도 너비(w), 높이(h)가 주어지고 둘째 줄부터 h개 줄은 지도가 주어지는데 지도는 1(땅), 0(바다)로 구성되어 있다.
지도 내 육지 간 가로, 세로, 대각선 방향으로 이어져있으면 한 섬으로 볼때 테스트 케이스 별로 섬의 개수를 출력하는 문제

from collections import deque
# 상하좌우 대각선 총 8방향
dx = [-1, 1, 0, 0, 1, -1, -1, 1]
dy = [0, 0, -1, 1, -1, -1, 1, 1]

def bfs(i, j):
    queue = deque()
    # 시작점 큐에 넣어주고
    queue.append((i, j))
    while queue:
        x, y = queue.popleft()
        # 8방향 탐색 진행
        for k in range(8):
            nx = x + dx[k]
            ny = y + dy[k]
            # 범위 내 다음 값이 육지인 경우
            if 0<=nx<h and 0<=ny<w and graph[nx][ny] == 1:
                # 큐에 넣고 다음 칸 바다 처리
                queue.append((nx, ny))
                graph[nx][ny] = 0
while True:
    w,h = map(int,input().split())
    # 입력값 중단 조건 걸어주고
    if w == 0 and h == 0 :
        break
    graph = []
    for _ in range(h):
        graph.append(list(map(int,input().split())))
	# 섬 개수
    answer = 0
    for i in range(h):
        for j in range(w):
        	# 현재 위치가 육지인 경우
            if graph[i][j] == 1:
            	# 섬 + 1처리 후 bfs탐색 진행
                # 이동할 수 있으면 같은 섬임을 의미
                answer += 1
                bfs(i,j)
    print(answer)

< 풀이 과정 >
대각선까지 포함해 총 8방향을 탐색하는 BFS문제

• 입력값
  while문으로 w,h와 h줄만큼의 그래프를 입력받고 현 위치가 육지이면 섬 + 1, bfs탐색 처리를 하여 같은 섬들의 여부를 체크해준다.
• bfs함수
  동일하게 진행하여 다음 위치가 육지인 경우, 방문한 후 바다로 처리해주고 큐에 다음위치 넣고 이어서 bfs진행!

🎈 17204 죽음의 게임

n명이 참가하는 게임에서 보성이의 번호 k개 주어지고 각 참여자 별로 자신이 지목한 사람의 번호가 주어진다.
이때 영기는 숫자 m을 불러 보성이가 걸리도록 해야하는데, 이때 불러야 하는 가장 작은 수를 구하는 문제

import sys
input = sys.stdin.readline
from collections import deque
# 입력값, 그래프, 방문 여부
n, k = map(int, input().split())
graph = [int(input()) for _ in range(n)]
visited = [0] * n

def bfs():
    queue = deque()
    # 시작값 큐에 넣고
    queue.append((0))
    # 큐가 빌때까지 반복
    while queue:
       # next 변수는 인덱스 느낌으로 뽑고 그래프[next]로 다음 값을 m으로 뽑는다
        next = queue.popleft()
        m = graph[next]
        # 만약 순환하지 않고, 방문한 적도 없다면 큐에 넣고 순환횟수 + 1
        if next != m and not visited[m]:
            queue.append(m)
            visited[m] = visited[next] + 1
            # k에 도달했을 때 리턴
            if m == k:
                return
bfs()
if visited[k]:
    print(visited[k])
else:
    print(-1)

🎈 11558 The Game of Death

플레이어는 각자 한명 지목, 처음 시작하는 사람이 K외치고 k번째 지목당한 사람이 걸리는 게임, 희현이는 1번째 주경이는 n번째일 떄 주경이를 걸리게 할 숫자를 출력하기
안걸리는 경우 0을 출력

def dfs(v):
	# 다음값 범위에 한해
    for i in game[v]:
    	# 방문하지 않았다면
        if not visited[i]:
        	# 기존 +1 후 dfs재귀
            visited[i] = visited[v] + 1
            dfs(i)
# 입력값 받기
t = int(input())
for _ in range(t):
    n = int(input())
    # 빈 리스트 만들어서 범위만큼 숫자 입력받고 인덱스 별로 추가하기
    game = [[] for _ in range(n+1)]
    for i in range(1, n+1):
        num = int(input())
        game[i].append(num)
    # 방문 여부 생성 후 dfs 1번 인덱스부터 탐색 진행
    visited = [0] * (n+1)
    dfs(1)
    if visited[n] > 0:
        print(visited[n])
    else:
        print(0)

< 풀이 과정 >
dfs 탐색을 활용하여 재귀로 구현하였다. 생각보다 오래걸린 문제.

• 입력값들을 받고 game이라는 빈 리스트도 만들어준 후 num 숫자를 받을 때마다 game 인덱스에 추가해준다.
• dfs 함수로 탐색 시 다음 값을 부여받고 방문하지 않았다면 +1 & dfs 재귀를 진행한다.
• 최종적으로, dfs 1부터 탐색을 시작해 n을 방문했다면 visited[n]을, 아닌 경우 0을 리턴한다.