[BOJ/백준] 13913 - 숨바꼭질 4 파이썬/Python3 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 시리즈 중에 4번째 공통된문제: 수빈이의 최소 소요 시간 추가된 요구 조건: 수빈이의 탐색 경로를 함께 제시 수빈이가 탐색한 경로를 어떻게 출력해야 될지를 고민했던 문제 [문제해결방식] 1. 수빈의 최소 이동 시간 1) 수빈이는 3가지 선택지가 있다. 현재 위치를 기준으로 -1칸, +1칸, ..
BOJ 1167 - 트리의 지름 파이썬 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름 구하기 - 정형화된 문제 패턴 1. 트리의 지름: 가장 먼 두 노드 사이의 거리 2. 선형 시간 안에 트리의 지름을 구하는 방법 1) 트리에서 임의의 노드 X를 설정 2) 노드 X를 기준으로 가장 먼 노드 Y를 탐색한다. 3) 노드 Y를 기준으로 가장 먼 노드 Z를 탐색한다. 4) 트리의 지름: 노드 Y와 노드 Z 사이의 거리 자..
[BOJ/백준] 23288 주사위 굴리기2 파이썬/Python3 주사위 굴리기 2 성공 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 1. 문제 풀이 1. 해당 문제는 기존에 출제되었던 주사위 문제의 업그레이드 2. 문제에 주어진 대로 구현하면 해결할 수 있는 문제 (주사위 인덱스를 변경하는 과정에서 실수가 잦을 수 있음) 3. bfs 탐색 알고리즘을 활용해서 주사위의 밑면의 수와 같은 수로 이루어진 칸이 몇 칸인지를 찾기 ..
치킨 배달 성공분류 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들..
문제 링크 - www.acmicpc.net/problem/3190 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이..