시나위

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 요약 트리의 지름 출력 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것 접근 1. 생각의 흐름 그래프 탐색 두번으로 진행하면 될 것 같다. 아무 점에서 시작해서 가장 먼 지점까지 탐색한다. 첫번째 탐색이 끝나면 가장 먼지점에서 두번째 탐색을 시작한다. // 1. 아무 노드에서 시작해서 가장 먼노드까지 간 다음, pair tmp; tmp = bfs({1, 0}); // 2. 가장 먼노드 노드에서 가장 먼노드까지 탐색 tmp = bfs({t..

https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 그래프탐색이 가미된 시뮬레이션 문제이고, 알고리즘 순서는 다음과 같다. 1. 입력 2. 시뮬레이션 (k번) 2-1. 주사위 이동 2-2. 점수 획득: 그래프 탐색 2-3. 다음 이동방향 결정 3. 출력 주사위 이동을 할때 주사위의 위치를 변경하면서 주사위 면도 변경했다. 주사위의 첫 면이 1 2 3 4 5 6 이라 하고 top이 1 bottom이 6이라고 할때 동쪽으로 굴러가면 ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백트래킹과 그래프 탐색 알고리즘을 모두 사용해야하는 문제이다 3개의 벽을 설치할 땐 백트래킹을 설치한 이후 바이러스가 전파되는 것은 그래프 탐색(BFS를 사용했다)을 하면된다. 바이러스 전파가 끝나면 이차원 배열에서 안전한 구역을 찾으면 된다. # import sys; input = sys.stdin.readline from collections import deque def bfs(): global N, M..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS로 진행했다. #include #include #include using namespace std; #define D(s) ((2 * (s)) % 10000) #define S(s) (((s) + 9999) % 10000) #define L(s) (((s) % 1000) * 10 + ((s) / 1000)) #define R(s) (((s) / 10) + (((s) % 10) *..

https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 그래프 탐색인데 1차원이라 생소하긴했지만 어려운 문제는 아니다. 단지 이전부터 많이 해왔던 것처럼 visit을 처음부터 잡아놓고 진행하면 메모리 초과가 나온다. 범위가 +-100,000,000이기 때문에 4 * 200,000,000 이므로 약 762MB 쯤 . 따라서 set이나 dictionary 자료구조를 사용해서 visit을 체크하면 된다. import sys; ..

https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 그래프 탐색을 활용하는 문제이다. BFS 로 이차원배열을 탐색했고 해당 구역에서 양과 늑대의 수를 확인한다음 한쪽 값만 내보내는 방식으로 진행했다. # import sys; input = sys.stdin.readline from collections import deque def bfs(i, j, _map, visit): global n, m ret = [0, 0] q = deque..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS로 풀수있는 쉬운 문제이다. from collections import deque def main(): n, k = map(int, input().split()) memo = [200000 for _ in range(100001)] q = deque() q.append(n) memo[n] = 0 answer = None while q: cur = q.popl..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 최단거리를 찾는 BFS 문제이다. 2차원 배열에서 방문하지 않은 점을 방문하면서 탐색하면 되고, 탐색도중 그람이 있으면 그 위치부터 맨해튼 거리값을 더해서 최소 값이 되는지 확인하면 된다. #include #include #include using namespace std; int map[100][100] = { 0 }; int N, M, T; int d[8] = { -1,0,0,..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net import sys;input = sys.stdin.readline from collections import deque # 탐색 def bfs(start, end, size, building): q = deque() q.append(start) visit = [[[0 for k in range(size[2] + 2)] for j in range(size[1] + 2)] for i in range(si..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net import sys; input = sys.stdin.readline from collections import deque def bfs(graph): q = deque() q.append(0) end = len(graph) - 1 visit = [-1 for _ in range(len(graph))] visit[0] = 0 while q: cur = q.popleft() if cur == ..