dotdotdot

[Python | 7562] 나이트의 이동

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

[Python | 5014] 스타트링크

https://www.acmicpc.net/problem/5014문제 설명강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)강호가 G층에 도착..

[Algorithm] 그래프와 순회(Graph traversal) 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

우리가 알고리즘을 공부하면서 마주치는 수많은 문제들 — 예를 들면 미로 탈출, 경로 찾기, 친구 관계 분석, 조직도 순회 등 —은 겉보기에는 다양해 보이지만 결국 "대상들 간의 연결 관계를 어떻게 탐색할 것인가"라는 문제로 귀결된다.이때 필요한 개념이 바로 그래프(Graph)다. 그래프는 노드(정점)과 간선(연결선)으로 이루어져 있으며, 정점은 어떤 대상(예: 도시, 사람, 웹페이지 등)을, 간선은 그들 사이의 관계(예: 도로, 친구 관계, 하이퍼링크 등)를 나타낸다. 그래프를 활용한 문제를 해결하려면, 그래프 자체를 어떤 방식으로 표현할 것인가가 먼저 결정되어야 한다.이를 위해 보통 그래프를 코드로 표현하는 두 가지 방식, 즉 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency ..