남남이루의 고군분투 🌳

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 예제 입력 1 복사 5 17 예제 출력 1 복사 4 동생 찾으러 가는..

문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 문제 요약 체스판 나이트..

문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다. 당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까? 입력 입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다...

너비우선 탐색은 그래프와 짝꿍

별도 함수없이 while queue로 푼다. 보통 최단거리 구하는 문제는 BFS 를 쓰더라..! 좌표가 경로를 벗어나지 않는 범위 내에서 1. 방문여부 확인, 2. 길이 맞는지 확인. 조건에 맞다면 방문여부 표시하고, 큐에 넣어서 다음 차례에 추가. 방문 여부를 확인할 때, 방문 여부에 (이전 방문에 +1 함으로써) 몇 번째 방문인지 적기. 결국 마지막 좌표(목적지) 입력시 몇 번째 방문인지(거리)가 나오게 됨. import sys sys.stdin = open('C:\\tech\\backjoon\\graph\\input4.txt','r') # 최단 거리 n,m = map(int, input().split()) graph = [list(map(int, input())) for _ in range(n)] ..

기본적인 DFS, BFS 문제인데, 아직 BFS가 익숙하지 않아서 BFS로 해봤다. 역시나 기본 프레임은 1260번이랑 비슷하다. import deque 쓰는 거랑 BFS함수 첫 줄에 deque 만들고 , while q : 로 하나씩 꺼내는 거 graph 만들 때 쌍방향으로 넣어주기 from collections import deque import sys sys.stdin = open('C:\\tech\\backjoon\\graph\\input.txt','r') input = sys.stdin.readline def BFS(node): q = deque() q.append(node) while q: node = q.popleft() for i in graph[node]: if visit2[i] == 0 ..

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) BFS 코드의 프레임 특징 from collections import deque ... def BFS(v): q = deque() q.append(v) while q: p = q.popleft() print(p) from collections import deque import sys sys.stdin = open('C:\\tech\\backjoon\\graph\\input3.txt','r') input = sys.stdin.readline res = [] def DFS(node): visit1[node] = 1 line = graph[node] for i in range(1,n+1): if line[i] == 1 and visit1[i] == 0: i..

노드가 추가될 때 마다, 그 인덱스를 출력하면 된다. 노드가 추가될 수 있다는건 루트 역할 하는 거고, 그 때 인덱스가 루트니까. import sys sys.stdin = open('input.txt','rt') input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n+1)] ans = [0] * (n+1) for i in range(n-1): a, b = map(int, input().split()) tree[a].append(b) tree[b].append(a) # print(tree) # [[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]] check = [False] * (n+1) ..

문제 트리 순회 출력하기 + 순회란, 노드와 간선(방향)으로 이루어진 트리를 어떤 순서로 탐색하는 지를 말한다. 이진 트리의 경우 꼭 가계도처럼 생겼는데, 가지의 상위에 있는 정점(노드)을 부모 노드라고 하고, 아래에 딸려있는 노드들이 짜-식들이다. 전위 순회는 기본적으로 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 탐색한다. 중위 순회는 왼쪽자식 -> 부모 -> 오른쪽 자식, 후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 부모 순이다. 제일 깊은 데까지 가서 출력하는데, 진행 경로를 선으로 이어서 그려보면 이해하기 쉽다. import sys sys.stdin = open('input.txt','rt') input = sys.stdin.readline n = int(input()) dic = {} fo..

문제 고장난 리모컨으로 채널을 이동하자! 어려웠던 점 str으로 자릿수별로 숫자맞추면서 접근해야 하는 줄 알았는데, 완전탐색이어서 숫자 하나씩 올리면서 접근해야 한다. 의외로 구현하기가 어려웠다. abs() 절대값 함수를 쓰지 않으면 음수 체크(if x < 0: x* -1)를 해줘야 해서 훨씬 코드가 길어진다. 수의 범위 수의 범위가 채널 범위 500,000를 그대로 쓰면 안되고, 리모컨 입력 접근 방향을 고려해야하기 때문에 자리수가 다를 수 있어 1,000,000으로 설정해야 한다. 작은 수에서 큰 수로 이동할땐 500,000 로 반대로 큰수에서 작은수로 내려올 때는 1,000,000 까지 target = int(input()) ans = abs(100 - target) # ++ or -- 로 이동할 ..