효팍이의 프로그래밍

백준 2206번 벽 부수고 이동하기 백준 2206번 벽 부수고 이동하기 큐의 마지막 원소에 1(벽뚫기가능), 0(벽뚫기불가능)을 넣는다. visited에는 각 좌표마다 [0,0]을 만들고 인덱스가 0이면 벽이미 뚫어서 못뚫고, 인덱스가 1이면 벽을 뚫 수 있다. 인덱스가 어딘지에 따라서는 벽뚫을 수 있는 여부를 판단하고, 별개로 원소 값이 0이면 방문가능하고, 1이상이면 방문 불가로 판단해서 다시는 그곳을 방문하지 않는다. 방문한 곳의 개수를 visited에 계속 쌓아가면서 나중에 그걸 답으로 뱉는다. 코드 from typing import List import sys input = sys.stdin.readline import sys from collections import deque class So..

백준 13549번 숨바꼭질3 백준 13549번 숨바꼭질3 bfs 다익스트라로 최소 거리를 계산함. 순간이동은 비용 0이라서 데크 appendleft()로 맨 앞에다 넣어줘야함. 코드 import sys import collections input = sys.stdin.readline N, K = map(int, input().split()) Q = collections.deque([(N, 0)]) visited = [False]*100001 while Q: loc, count = Q.popleft() if loc == K: print(count) break if not visited[loc]: visited[loc] = True if 0

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

문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 입력1 7 1 6 6 3 3 5 4 1 2 4 4 7 출력1 4 6 1 3 1 4 입력2 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12 출력2 1 1 2 3 3 4 4 5 5 6 6 코드 from sys import stdin import collections class Solution: def..

문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한..