Coding 공부

import sys

input = sys.stdin.readline
def findprimenumber():
    global prime_number
    prime_number[1] = False
    prime_number[0] = False
    for i in range(2,10001):
        if prime_number[i]:
            for j in range(i+i,10001,i):
                prime_number[j] = False





T = int(input())
prime_number = [True]*10001
findprimenumber()
for _ in range(T):
    A,B = map(int,input().split())
    result = 'Impossible'
    visited = [-1] * 10001
    if A == B:
        print(0)
    else:
        stack = [A]
        cnt = 0
        while stack:
            new_stack = []
            for number in stack:
                number_list = list(map(int,list(str(number))))
                for ind in range(4):
                    if ind == 0:
                        for k in range(1,10):
                            if number_list[ind] != k:
                                new_number = k*1000 + 100*number_list[1] + 10*number_list[2] + number_list[3]
                                if visited[new_number] == -1 and prime_number[new_number]:
                                    visited[new_number] = cnt+1
                                    new_stack.append(new_number)
                    else:
                        for k in range(10):
                            if number_list[ind] != k:
                                new_number = number - number_list[ind]*(10**(3-ind)) + k*(10**(3-ind))
                                if visited[new_number] == -1 and prime_number[new_number]:
                                    visited[new_number] = cnt+1
                                    new_stack.append(new_number)
            if B in new_stack:
                result = cnt + 1
                break
            stack = new_stack[:]
            cnt += 1
        print(result)
        
        

문제는 소수를 구하는 것과 BFS를 활용하면 되는 문제였다.

먼저 자신만의 방법으로 문제에서 주어진 10000 까지의 소수를 구한다.

나는 단순하게 반복문을 통해서 구했고, True False로 구분이 되게 해주었다.

이 상황에서 주어진 넘버에서 각자리 수를 변경하면서, 방문하지 않았고 소수일때에 new_stack에 넣어주는 방식으로 했다.

import sys

input = sys.stdin.readline


prime_number = [True]*10000
prime_number[0] = False
prime_number[1] = False

for k in range(2,10000):
    if prime_number[k]:
        for j in range(k+k,10000,k):
            prime_number[j] = False

T = int(input())

for _ in range(T):
    A,B = map(int,input().split())
    if A == B:
        print(0)
    else:
        visited = [True]*10000
        result = 'Impossible'
        stack = [A]
        cnt = 0
        while stack:
            new_stack = set()
            for number in stack:
                for k in [1,10,100,1000]:
                    fall_number = number - (number//k)%10*k
                    for i in range(10):
                        new_number = fall_number + i *k
                        if prime_number[new_number] and visited[new_number] and new_number >= 1000:
                            visited[new_number] = False
                            new_stack.add(new_number)
            if B in new_stack:
                result = cnt + 1
                break
            stack = list(new_stack)[:]
            cnt += 1
        print(result)

 좀 더 깔끔한 방법으로 자리수 변경을 한 방식이다. 주어진 넘버에서 바꾸고 싶은 자리수로 나눈 몫의 10으로 나눈 나머지를 구하면, 해당 자리수를 구할 수 있다. 이 방식을 이용해서, 구현했다.

from itertools import permutations
from collections import deque
def outOfrange(x,y):
    if 0 > x or x >3 or y<0 or y>3:
        return True
    return False

def dfs(start,end,copy_board):
    dp = [[-1]*4 for _ in range(4)]
    dp[start[0]][start[1]] = 0
    stack = deque()
    stack.append((start[0],start[1]))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            repeat = 0
            while True:
                nx = x + dx[i]*repeat
                ny = y + dy[i]*repeat
                if outOfrange(nx+dx[i],ny+dy[i]) or (repeat!=0 and copy_board[nx][ny]):
                    break
                repeat += 1
            for re in (1,repeat):
                nx = x + dx[i] * re
                ny = y + dy[i] * re
                if outOfrange(nx,ny):
                    continue
                if dp[nx][ny] == -1:
                    dp[nx][ny] = dp[x][y] + 1
                    stack.append((nx,ny))
                    if dp[end[0]][end[1]] != -1:
                        return dp[end[0]][end[1]]
    return dp[end[0]][end[1]]



def find_command(x,y,find_card,copy_board):
    dis1 = dfs((x,y),find_card[0],copy_board)
    dis2 = dfs(find_card[0],find_card[1],copy_board)
    return dis1+dis2




def solution(board, r, c):
    answer = float('inf')
    card_list = [[] for _ in range(7)]
    card_numbers = set()
    for x in range(4):
        for y in range(4):
            if board[x][y]:
                card_list[board[x][y]].append((x,y))
                card_numbers.add(board[x][y])

    card_cnt = len(card_numbers)
    for combi in permutations(card_numbers):
        predict_dict = {}
        for k in range(1<<card_cnt):
            distance = 0
            mouse_cursor_x = r
            mouse_cursor_y = c
            copy_board = [row[:] for row in board]
            temp = ''
            for ind,num in enumerate(combi):
                start = int(bool((k&1<<(ind))))
                end = (start+1)%2
                temp += str(start)
                find_card = [card_list[num][start],card_list[num][end]]
                if not predict_dict.get(temp):
                    distance += find_command(mouse_cursor_x,mouse_cursor_y,find_card,copy_board)
                    predict_dict[temp] = distance
                else:
                    distance = predict_dict[temp]
                mouse_cursor_x = card_list[num][end][0]
                mouse_cursor_y = card_list[num][end][1]
                copy_board[card_list[num][start][0]][card_list[num][start][1]] = 0
                copy_board[card_list[num][end][0]][card_list[num][end][1]] = 0
                if distance > answer:
                    break
            if answer > distance:
                answer = distance
    return answer+2*card_cnt


a = solution([[1,0,2,0],[6,2,4,0],[0,0,1,0],[6,0,0,4]],1,0)
print(a)

문제 자체는 BFS+순열+조합으로 간단해보였지만, 구현하는데 난이도가 컸던 문제였다.

기본 풀이 자체는 다음과 같다.

카드번호 1,2,3이 있다고 하면

1,2,3을 순열로 먼저 없앨 카드별 순서를 정해준다.

그리고 각 카드는 2장씩 있으므로, A,B 가 있다고 치면

1A->1B

1B->1A는 다를 것이다.

이 모든 경우를 돌려서 결과를 얻는 것이다.

그래서 먼저 나는 card_numbers에 이 보드에 있는 카드번호들을 저장해두고 permutations 모듈을 사용해서 순열을 만들었다 그리고 난뒤, 카드의 앞뒷면을 정해주기 위해 조합을 만들었다.

만약 우리가 카드가 3장이 있다고 하면 이 카드의 앞뒷면을 만들수 있는 가짓수는

000

001

010

011

100

101

110

111

이런식으로 총 8가지가 있을수 있다. 위의 가지수를 각비트로 봐보면 0~7까지인걸 알수 있다. 그러므로 저는 카드의 개수가 N이라고 하면, 2**N 만큼 range를 돌리고, 각 permutations으로 나오는 각각의 카드 index와 비트연산을 해서, 해당 카드의 앞뒷면의 순서를 결정해주었다.

이렇게 한뒤 현재 커서위치 -> 먼저 찾을 카드위치 -> 나중 찾을 카드위치 순으로, bfs를 돌렸다.

bfs를 돌릴때, ctrl 이동과 일반적인 한칸이동을 동시에 시행했다. 범위 밖을 나가던지, 아니면 카드가 있는 위치이던지, 그 위치까지의 길이를 기억해놓은뒤, 그 만큼을 dp라는 visited를 담당하는 행렬에 저장을해주었다. 그리고 우리가 찾는 목적지에 도착하면, return 해주는 방식으로 했다.

이렇게 bfs를 전부 돌린뒤에는 copy한 board에서 우리가 현재 뒤집은 카드들의 정보를 0으로 바꿔주고, 마우스 커서위치는 마지막 카드위치로 바꿔주는 작업을 해준다.

위 풀이 방식은 아슬아슬하게 시간을 통과한지라 여러부분에서 시간을 줄여주었다. 위에서 했듯이 bfs에서 매번 도착지점을 판별해주는 것이 첫번째 방법이었고, distance가 저장된 answer 보다 커지면 탐색을 중단해주는것도 그 방안이었다.

이렇게 구한 answer에 현재 카드의 종류의 2배만큼 더해서 출력해주면된다.

from collections import deque
import functools
def solution(board,r,c):
    card_dict = [[] for i in range(7)]
    card_tuple = set() 
    for x in range(4):
        for y in range(4):
            if board[x][y]:
                card_dict[board[x][y]].append((x,y))
                card_tuple.add(board[x][y])
    card_tuple = tuple(card_tuple)

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    def outOfrange(x,y):
        if 0 > x or x >3 or y<0 or y>3:
            return True
        return False

    @functools.lru_cache(maxsize=None)
    def bfs(s,t,cards):
        if s == t:
            return 0
        stack = deque()
        stack.append((s[0],s[1],0))
        visited = set()
        while stack:
            x,y,cnt = stack.popleft()
            for i in range(4):
                repeat = 0
                while True:
                    nx = x + dx[i]*repeat
                    ny = y + dy[i]*repeat
                    if outOfrange(nx+dx[i],ny+dy[i]) or (repeat != 0 and board[nx][ny] in cards):
                        break
                    repeat += 1
                for re in [1,repeat]:
                    nx = x + dx[i]*re
                    ny = y + dy[i]*re
                    if outOfrange(nx,ny):
                        continue
                    if (nx,ny) == t:
                        return cnt + 1
                    if (nx,ny) not in visited:
                        visited.add((nx,ny))
                        stack.append((nx,ny,cnt+1))

    @functools.lru_cache(maxsize=None)
    def find_card_short_count(cur_position,cards):
        if len(cards) == 0:
            return 0
        min_distance = float('inf')
        for pick_card in cards:
            position1,position2 = card_dict[pick_card]
            remain_cards = tuple(card for card in cards if card != pick_card)
            direction1 = bfs(cur_position,position1,cards) + bfs(position1,position2,cards) + find_card_short_count(position2,remain_cards)
            direction2 = bfs(cur_position,position2,cards) + bfs(position2,position1,cards) + find_card_short_count(position1,remain_cards)
            min_distance = min(min_distance,direction1,direction2)
        return min_distance

    answer = len(card_tuple)*2 + find_card_short_count((r,c),card_tuple)
    return answer


a = solution([[1, 0, 0, 3], [2, 0, 0, 0], [0, 0, 0, 2], [3, 0, 1, 0]], 1, 0)
print(a)

위의 풀이 대신 이 풀이는 프로그래머스의 다른사람풀이를 보고 공부하면서 쓴 풀이다.

자세한 설명은 http://www.teferi.net/ps/problems/programmers/72415 이 링크를 참조하길 바란다.

기본적인 풀이는 비슷하다. 대신 이 풀이는 위에서 복잡하게 비트연산을 통해 결정하는 것이 아닌, 재귀함수를 통해, 순열과 조합을 구현했고, functools.lru_cache를 통해 메모라이즈를 해주었다.

이 두 방식을 통해 시간이 획기적으로 줄어들었다.

이 풀이는 크게 2가지의 함수로 나뉠수 있다. find_card_short_count라는 함수와 bfs 함수이다.

bfs는 A->B까지 가는 최소 명령어를 찾아주는 것이다. 여기서 카드의 위치를 판단하는것은 cards라는 tuple을 통해, 있는지 판별을 해준다.

여기서 중요한것은 find_card_short_count라는 함수이다. 이 함수의 역할은 재귀를 통해 순열을 만드는 것이다.

cur_position은 현재 커서의 위치이고, cards는 현재 남아있는 카드들의 번호들이다.

이 cards를 반복문을 돌리면서 그 카드를 제거할 카드라 생각하고, cards에서 현재 선택한 card를 제외한 나머지 카드들을 remain_cards로 남겨준다.

위에서 설명했던 것처럼 한 카드에서도 먼저 제거할 카드를 선택을 해야한다. 그 방법으로 direction1과 direction2로 나뉘어서 해주었다.

한 카드에서 position1 과 position2가 있다고 하면 제거할 수 있는 방법은 두가지이다.

현재 커서위치 -> position1까지의 거리를 구해주고 position1 -> position2 까지의 거리를 구해준다.
그러면 마지막 커서의 위치는 position2가 되고 position2와 remain_cards를 가지고 find_card_short_count를 해주면 된다.

이런 방식으로 현재 커서 위치 -> position2 -> position1도 똑같이 해준다.

direction1 = bfs(cur\_position,position1,cards) + bfs(position1,position2,cards) + find\_card\_short\_count(position2,remain\_cards)

direction2 = bfs(cur\_position,position2,cards) + bfs(position2,position1,cards) + find\_card\_short\_count(position1,remain\_cards)

이 식들이 위에서 설명해준것을 구현한 것이다.

여기서 중요한 역할을 하는 것은 functools.lru_cache 라는 데코레이터이다.

이 데코레이터의 역할은 함수의 호출을 기억해주는 것이다. 똑같은 입력값이 들어온 함수들을 기억해서, 다음번에 호출이 되는 경우 함수를 한번더 실행하는 것이 아닌, 기억한 결과값을 그대로 주는 것이다.

그렇기 때문에 이 데코레이터를 썼을 때, 메모라이즈를 해준것이기 때문에, 재귀함수를 쓰면서도 시간을 줄일 수 있다.

다음과 같이 시간을 100ms 이하로 줄일 수 있다.

functools.lru_cache를 쓰지 않으면 시간의 압박이 크다.

위의 풀이가 아닌 DP를 활용한 풀이를 보고 싶은 분들은 https://www.youtube.com/watch?v=FX9n1PFv2K4 해당 유튜브를 참조하길 바랍니다.

import sys
from collections import deque

input = sys.stdin.readline
def bfs():
    global INF,result
    stack = deque()
    stack.append((0,0,1,0))
    visited = [[[INF for z in range(2)] for _ in range(M)] for _ in range(N)]
    visited[0][0][0] = 1
    visited[0][0][1] = 1
    while stack:
        x,y,dis,wall_cnt = stack.popleft()
        if x== N-1 and y == M-1:
            if result > dis:
                result = dis
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx< N and 0<= ny < M:
                if visited[nx][ny][wall_cnt] > dis + 1 and wall_cnt <=1:
                    if arr[nx][ny] == '1' and not wall_cnt:
                        visited[nx][ny][wall_cnt] = dis + 1
                        stack.append((nx,ny,dis+1,wall_cnt+1))
                    elif arr[nx][ny] == '0':
                        visited[nx][ny][wall_cnt] = dis +1
                        stack.append((nx,ny,dis+1,wall_cnt))


N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(input()) for _ in range(N)]
wall = []
INF = float('inf')


result = INF
bfs()
if result == INF:
    print(-1)
else:
    print(result)

처음 풀었던 방식은 BFS를 하면서 방문을 했는지 안했는지를 하나의 축으로 추가해서 visited에 표시를 해주는 거였다.

import sys
from collections import deque


input = sys.stdin.readline


N,M = map(int,input().split())
arr = [list(input()) for _ in range(N)]
INF = float('inf')
distance_front = [[INF]*M for _ in range(N)]
distance_back = [[INF]*M for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
stack1 = deque()
stack2 = deque()
distance_front[0][0] = 1
distance_back[N-1][M-1] = 0

stack1.append((0,0))
stack2.append((N-1,M-1))

while stack1:
    x,y = stack1.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx <N and 0<= ny <M:
            if distance_front[nx][ny] == INF:
                distance_front[nx][ny] = distance_front[x][y] +1
                if arr[nx][ny] == '0':
                    stack1.append((nx,ny))

while stack2:
    x,y = stack2.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx <N and 0<=ny <M:
            if distance_back[nx][ny] == INF:
                distance_back[nx][ny] = distance_back[x][y] + 1
                if arr[nx][ny] == '0':
                    stack2.append((nx,ny))

result = distance_front[N-1][M-1]

for x in range(N):
    for y in range(M):
        if arr[x][y] == '1':
            result = min(result,distance_front[x][y]+distance_back[x][y])

if result != INF:
    print(result)
else:
    print(-1)

개선된 방식은 0,0에서 BFS를 돌리고, 목표지점인 (N-1,M-1)에서 BFS를 돌린다. 그리고 BFS를 돌리면서 최단거리를 저장해놓는다.

그리고 첫번째 돌린 BFS의 최단거리에서 목표지점까지의 최단거리를 구하고,

벽을 부셨을때 최단거리는 두개의 BFS의 합을 통해 구한다.

벽인 지점 (A,B)가 있으면, 첫번째 돌린 BFS의 (A,B)의 값과 두번째 돌린 BFS의 (A,B)을 합쳐주면 그 벽을 부셨을때의 최단 이동거리가 된다.

위와 같이 할려면 초기값을 주의해야하는데, 첫번째 BFS의 초기값은 1이고, 두번째 BFS는 0이다.

from collections import deque
def bfs():
    global N,M
    stack = deque()
    stack.append((N,M))
    visited = set()
    visited.add((N,M))
    while stack:
        x,y = stack.pop()
        if x == 1 and y == 1:
            return 'yes'
        if dict_array.get(x*y):
            for nodes in dict_array[x*y]:
                if nodes not in visited:
                    visited.add(nodes)
                    stack.append(nodes)
    return 'no'

N = int(input())
M = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dict_array = {}
for x in range(N):
    for y in range(M):
        if dict_array.get(arr[x][y]):
            dict_array[arr[x][y]].append((x+1,y+1))
        else:
            dict_array[arr[x][y]] = [(x+1,y+1)]

if dict_array.get(N*M):
    print(bfs())
else:
    print('no')

 처음으로 풀어본 영어로 된 문제이다. 영어로 되어있는 것을 제외하고는 그렇게 어렵지 않은 문제이고, python으로 통과한 사람들이 적다보니 통과시간에 걸릴까 걱정했는데 처음에는 아슬아슬하게 통과했다.

제한시간 2초인데 1.9초가 떴었다.

문제를 봐보면 일반적인 방탈출 게임 같아보인다. 하지만 여기서는 상하좌우로 움직이던 일반적인 bfs가 아닌 현재 내가 밟은 위치에 있는 값에 따라 움직일 수 있는 위치가 달라진다.

그 방법은 현재 내가 밟고있는 index에 위치한 값의 약수 쌍의 좌표로만 옮겨갈수 있다

예를 들면 

3 10 8 14

1 11 12 12

6 2 3 9

문제에 있는 3*4 배열을 봐보면

처음 시작 위치는 (1,1)이다. 그 위치에 있는 값은 3이므로, 3의 약수는 (1,3) (3,1)로 갈 수 있다.

그러면 다음 위치는 (1,3) 이나 (3,1)이 될수 있는데

만약 (1,3)이라한다면 (1,3)에 있는 값은 8 이다. 8의 약수는 (1,8) (2,4),(4,2),(8,1)이 존재할 수 있는데,

(4,2),(8,1),(1,8)은 범위를 넘어가므로, 갈 수 없다.

그러므로 (2,4)로 갈 수 있다.

이런식으로 jump를 해서 우측 최하단에 도착하는 게임이다.

도착이 가능하면 yes 불가능하면 no를 출력해주면 된다.

처음에는 약수를 구하는 생각을 해봤는데, 주어진 행렬의 최대가 1000*1000이다. 거기에 주어지는 최대값은 100만이다.

100만에 대한 모든 약수를 구하다보면  10억번 정도의 연산이 필요로 할 것 같아서, 폐기했다.

그 다음으로 생각한 방법이 위의 풀이이다.

역으로 올라가보자는 것이다.

우리가 (N,M)에 도착하기 위해서 무조건 배열 내에 N*M인 값이 존재해야한다.

1. N*M을 가지고 있는 위치를 찾아간다.

2. 그 위치에 도달할 수 있는 값을 찾아서 또 이동한다.

위와 같은 로직을 생각했다.

즉, 위의 예제로 설명하면

(3,4)에 도착하기 위해서는 12의 값이 필요한데, 이 12를 가진 발판의 위치는 (2,3),(2,4)이다.

(2,3)에 도착하기 위해서는 6의 값이 필요한데 6이 존재하는 위치는 (3,1)이다.

(2,4)에 도착하기 위해서는 8의 값이 필요한데 8이 존재하는 위치는 (1,3)이다.

(3,1),(1,3)에 도착하기 위해서는 3의 값이 필요한데 3이 존재하는 위치는 (1,1) 아니면 (3,3)이다.

이렇게 해서 풀 수 있다.

from collections import deque
def bfs():
    global N,M
    stack = deque()
    stack.append((N,M))

    while stack:
        x,y = stack.pop()
        if x == 1 and y == 1:
            return 'yes'
        if dict_array.get(x*y):
            for nodes in dict_array[x*y]:
                stack.append(nodes)
            del dict_array[x*y]
    return 'no'

N = int(input())
M = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dict_array = {}
for x in range(N):
    for y in range(M):
        if dict_array.get(arr[x][y]):
            dict_array[arr[x][y]].append((x+1,y+1))
        else:
            dict_array[arr[x][y]] = [(x+1,y+1)]

if dict_array.get(N*M):
    print(bfs())
else:
    print('no')

이 코드는 위의걸 개선한 코드이다. 방문표시를 하기위해서 visited를 쓰는대신 한번 방문한 곳은 전부 지워버렸다.

from collections import deque


def dfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    stack = [V - 1]
    
    while stack:
        x = stack.pop()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N - 1, -1, -1):
            if graph[x][k] >= 1:
                graph[x][k] = 0
                graph[k][x] = 0
                stack.append(k)
    
    return result


def bfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    q = deque()
    q.append(V - 1)

    while q:
        x = q.popleft()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N):
            if graph[x][k] >= 1:
                graph[x][k] -= 1
                graph[k][x] -= 1
                
                q.append(k)
    
    return result



N, M, V = map(int, input().split())
arr = [list(map(int ,input().split())) for _ in range(M)]

dfs_res = dfs()
for i in range(len(dfs_res)):
    print(dfs_res[i], end=" ")
print()
bfs_res = bfs()
for i in range(len(bfs_res)):
    print(bfs_res[i], end=" ")
print()

DFS와 BFS 문제이다.

웹개발 중 코테 대비하면서 연습용으로 오랜만에 풀었던 문제라, 코드가 별로이다.

def solution(start,flag):
    global N
    stack = [start]
    visited = [True]*(N+1)
    ind = 0
    if flag:
        ind = -1
    result = []
    while stack:
        node_number = stack.pop(ind)
        if not visited[node_number]:
            continue
        visited[node_number] = False
        result.append(node_number)
        for next_node in sorted(graph[node_number],reverse=flag):
            if visited[next_node]:
                stack.append(next_node)
    return result




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)



print(*solution(V,True))
print(*solution(V,False))

 기본적인 풀이는 같다. DFS이냐, BFS이냐에 따라 트리거를 주었고, DFS일때는 pop하는 index를 -1로 아니면 0으로 주었다.

그리고 dfs는 뒤에서부터 pop이 되므로, graph를 내림차순으로 정렬해주고, bfs는 오름차순으로 정렬해주는것만 다르다.

import collections


def bfs(i):
    global N,graph,result
    stack = collections.deque()
    stack.append((i,0))
    visited = [True] * (N+1)
    visited[i] = False
    while stack:
        ind,dep = stack.popleft()
        for next_ind in graph[ind]:
            if visited[next_ind]:
                stack.append((next_ind,dep+1))
                visited[next_ind] = False
    return dep







N = int(input())
graph = [[] for _ in range(N+1)] 
while True:
    a,b = map(int,input().split())
    if a == -1 and b == -1:
        break
    graph[a].append(b)
    graph[b].append(a)


result = [50]*(N+1)
for i in range(1,N+1):
    result[i] = bfs(i)


min_list = [min(result),result.count(min(result))]
print(*min_list)
min_result = []
for i in range(1,N+1):
    if result[i] == min_list[0]:
        min_result.append(i)
print(*min_result)

 친구의 깊이를 물어보는 문제였다. 문제에서 들어오는 최대 인원이 50이므로 50으로 해놓은 상태에서 바꿨다.

그리고 깊이를 물어보는 것이기 때문에, DFS가 아닌 BFS를 이용해서 최단거리를 깊이로 생각해서 풀었다.

# 플로이드 와샬

N = int(input())
graph = [[0]+[50]*N if i!=0 else [50]*(N+1) for i in range(N+1)]
while True:
    a,b = map(int,input().split())
    if a == b == -1:
        break
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1,N+1):
    graph[i][i] = 0

for k in range(1,N+1):
    for from_node in range(1,N+1):
        for to_node in range(1,N+1):
            if graph[from_node][to_node] == 1 or graph[from_node][to_node] == 0:
                continue
            elif graph[from_node][to_node] > graph[from_node][k] + graph[k][to_node]:
                graph[from_node][to_node] = graph[from_node][k] + graph[k][to_node]


min_result = list(map(max,graph))

print(min(min_result),min_result.count(min(min_result)))
min_ind = []
for ind,val in enumerate(min_result):
    if val == min(min_result):
        min_ind.append(ind)
print(*min_ind)

플로이드 와샬 방식으로 푼 방식이다.

기본 원리는 같지만 연결을 표현한 방식이 달라졌을 뿐이다.

# 6593 상범 빌딩
from collections import deque


def printresult(flag,sec):
    if flag:
        return f'Escaped in {sec} minute(s).'
    else:
        return 'Trapped!'


while True:
    L,R,C = map(int,input().split())
    if L+R+C == 0:
        break
    building = []
    dx = [-1,1,0,0,0,0]
    dy = [0,0,-1,1,0,0]
    dz  = [0,0,0,0,-1,1]
    startpoint = []
    endpoint = []
    for ind in range(L):
        temp = []
        for x in range(R):
            input_list = list(input())
            for y,val in enumerate(input_list):
                if val == 'S':
                    startpoint = [x,y,ind]
                elif val == 'E':
                    endpoint = (x,y,ind)
            temp.append(input_list)
        building.append(temp)
        input()
    # 층,행,열
    stack = deque()
    stack.append(startpoint)
    building[startpoint[2]][startpoint[0]][startpoint[1]] = '#'
    minutes = 0
    flag = False
    while stack:
        new_stack = []
        minutes += 1
        for x,y,z in stack:
            for i in range(6):
                nx = x + dx[i]
                ny = y + dy[i]
                nz = z + dz[i]
                if 0<=nx<R and 0<=ny<C and 0<=nz<L:
                    if building[nz][nx][ny] != '#':
                        if (nx,ny,nz) == endpoint:
                            flag = True
                            break
                        else:
                            building[nz][nx][ny] = '#'
                            new_stack.append((nx,ny,nz))
        if flag:
            print(printresult(flag,minutes))
            break

        stack = new_stack[:]
    if not flag:
        print(printresult(flag,minutes))

BFS 관련 문제이다. 문제를 제대로 안 읽어서 input값을 제대로 안 받았더니 많이 틀렸던 문제이다.

일반적인 BFS를 3차원으로 바뀐것과 동일하고, range를 많이 쓰면 메모리 초과가 날 수 있으니 조심해서 풀면 되는 문제이다.

# # 1600 말이 되고픈 원숭이
from collections import deque
K = int(input())
W,H = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(H)]

stack = deque()
stack.append((0,0,0,K))

visited = [[[0 for z in range(K+1)] for y in range(W)] for _ in range(H)]
visited[0][0][0] = 1
horse_move = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]
move = [(-1,0),(1,0),(0,-1),(0,1)]
result = -1
while stack:
    x,y,cnt,horse_cnt = stack.popleft()
    if x+1 == H and y+1 == W:
        result = cnt
        break
    for dx,dy in move:
        nx = x + dx
        ny = y + dy
        if 0<=nx<H and 0<=ny<W:
            if not arr[nx][ny]:
                if not visited[nx][ny][horse_cnt]:
                    stack.append((nx,ny,cnt+1,horse_cnt))
                    visited[nx][ny][horse_cnt] = 1
    if horse_cnt:
        for dx,dy in horse_move:
            nx = x + dx
            ny = y + dy
            if 0<=nx<H and 0<=ny<W:
                if not arr[nx][ny]:
                    if not visited[nx][ny][horse_cnt-1]:
                        stack.append((nx,ny,cnt+1,horse_cnt-1))
                        visited[nx][ny][horse_cnt-1] = 1



print(result)

이 문제는 두가지의 이동방식이 있고, 그것을 구분해서 BFS를 해주면 된다. 하지만 여기서 주의할 점은 다음과 같다.

방문 표시를 체크를 하는데 주의를 해야한다.

1

4 4

0 0 0 0

0 0 0 0

0 0 1 1

0 0 1 0

위와 같이 되어 있다고 했을시, 방문표시를 따로 구분하지 않고 한가지로 했을시에는, 말로 왔는지, 원숭이로 왔는지 정확히 모르기 때문에 원하는 답이 안나올 수 있다.

그래서 visitied를 기존의 x,y 좌표 뿐만아니라 말의 이동회수를 기준까지 포함해서, 방문표시를 해주었다. 이부분만 조심해주면, 문제를 풀 수 있다.