본문 바로가기

728x90
반응형

그래프 이론

(13)
[Python] 백준 12851번 문제, 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 수빈이가 동생과 숨바꼭질 하고 있는데 수빈이가 동생을 찾는 가장 빠른 시간이 몇 초 후이며, 가장 빠른 시간으로 찾는 방법이 몇 가지인지 구하는 문제이다. 수빈이가 X(0 ≤ X ≤ 100,000)에 있다고 가정 했을 때, 1초에 { X-1, X+1, 2X }으로 이동할 수 있다. 이렇게 몇 초후에 동생이 있는 K(0 ≤ K ≤ 100,000)에 도달하는지 구..
[Python] 백준 16173번 16174번 문제, 점프왕 쩰리 시리즈 https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net https://www.acmicpc.net/problem/16174 이 문제는 주어진 맵 밖을 벗어나거나 -1(맨 우측 하단)에 도달하지 못하면 게임에 져서 "Hing"을 출력하고 -1에 도달하면 게임에서 승리해 "HaruHaru"를 출력한다. 세부 조건으로 시작 좌표는 맨 좌측 상단인 (0, 0)이고 움직이는 방향은 우측 또는 하단이지만, 움직일 수 있는 거리는 현재 내가 있는 칸의 숫자이다. 이런..
[Java] 백준 16173번 문제, 점프왕 쩰리(Small) https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 게임 조건은 다음과 같다. 1. ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다. 2. ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다. 3. ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할..
[Python] 백준 14502번 문제, 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 연구소 정보(0: 빈 칸, 1: 벽, 2: 바이러스)가 주어지고 벽을 세 개 세웠을 때, 바이러스가 없는 안전한 빈 칸의 갯수를 구하는 문제이다. 브루트포스 알고리즘이기 때문에 벽을 세 개 놓을 수 있는 모든 경우를 돌며 BFS를 통해 바이러스를 전파시킨 다음에 전파가 끝난 다음에 빈 칸의 갯수를 세어 최대값만을 구한다. 벽을 세 개 놓을 수 있는 모든 경우는 [0][j]부터 [N-1][M-1]까지 탐색하면서..
[Python] 백준 2636번 문제, 치즈 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 이 문제는 너비우선탐색을 이용한 시뮬레이션 문제이다. 보드판 위에 치즈가 있을 때, 치즈는 1개의 블록의 집합으로 이루어져있는데 1시간마다 치즈의 겉테두리이 녹는다. 즉, 치즈의 테두리가 1시간마다 사라진다는 것이다. 치즈 중간이 비어있어도 겉테두리와 연결되어 있지 않다면 녹지 않으며, 무조건 겉테두리만 1시간에 한 번씩 녹는다. 그래서 너비우선탐색으로 치즈의 겉테두리를 찾아낸 다음에 겉테두리 값을 1(치즈)에서 0..
[Python] 백준 6118번 문제, 숨바꼭질 https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2
[Python/미해결] 백준 1068번 문제, 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제에서는 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력하는 것이다. 트리 구조를 class를 통해 만든 다음에 remove_target와 같은 값을 가진 노드를 삭제했다. 그렇다면 탐색을 통해 리프 노드의 개수를 구하기만 하면 된다. 따라서 전위 순회를 통해 순차적으로 노드를 확인하면서 리프 노드(자식의 개수가 0인 노드)라면 count를 증감시켜준다. node_list[]: inde..
[Python] 백준 1245번 문제, 농장 관리 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1

728x90
반응형