MuviSsum

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제: 주어진 트리에서 트리의 지름을 구하여라 문제 이해하기!! 해당 문제는 1167번 문제와 같은 문제입니다.문제의 설명과 풀이 방법은 이전 글을 참고하시거나 해당 링크를 따라가시면 됩니다!링크: https://txegg.tistory.com/166 [BOJ] 1167. 트리의 지름 www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저..

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제: 주어진 트리에서 트리의 지름을 구하여라 문제 이해하기!! 트리의 지름이란 원본 문제를 보면 설명이 나와있는데요, 임의의 정점에서 임의의 정점까지의 거리가 최대인 것을 뜻합니다. 그럼 어떻게 구해야할까요? 정점의 갯수는 10만으로 플로이드-와샬 알고리즘은 못 씁니다. 그럼 다익스트라를 써도 될까요? 으음.. DP로 저장한다고 하더라도 여러 정점을 살펴봐야하기에 힘들죠. 좀 더 기본적인 방향..

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제: 집들이 연결되어 있는 단지를 파악하고 총 단지의 수와 각 단지의 집이 몇개인지 파악하라. 문제 이해하기!! 해당 문제는 딱 명확한 완전탐색이었습니다. BFS, DFS든 상관은 없구요, visit 배열로 방문체크만 해준다면 바로 풀리는 문제입니다. 제가 푼 방식을 설명하자면, 1. 입력받은 배열을 for문으로 돌려, 아직 방문하지 않은 곳이고 집이 있는 곳이라면 DFS를 수행합니다. 2. DFS구현: DFS..

www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제: DSLR이라는 4가지 명령어로 주어진 숫자를 목표값으로 최소한의 명령을 통해 바꾸어라. 문제 이해하기!! 아, 이 문제 너무 깐깐한 문제였습니다. 문제에 테스트케이스의 수가 나와있지 않고 시간제한이 6초라니.... 일단 알아본봐로는 테케 수가 최대 1만개라고 합니다! 참고^^ 이 문제를 풀려면 BFS 방법을 써야하는데요, 일단 4가지 명령어는 쉽게 구현됩니다. 하지만 여기서 DFS를 써버리면..

www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제: 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력하라. 문제 이해하기!! 구역을 나누는 것을 구해야 되는 문제입니다. 문제에서 나오는 적록색약은 미끼로 그냥 두 번 "R"을 "G"로 바꾸어 한 번 더 구하면 되는 문제였습니다. 그렇다면 어떻게 구역을 나눌까요. 저는 DFS로 완전탐색을 실시하였습니다. 해당 구역들을 찾기 위해서는 각 구역..

www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제: 뱀과 사다리 게임에서 주사위를 최소로 굴려 1부터 100까지 가장 빠르게 도착할 수 있게 하라. 문제 이해하기!! 뱀과 사다리 게임은 예전에 많이 해봤던 추억의 놀이죠. 그래서 문제를 쉽게 이해할 수 있었던 것 같습니다. 1부터 100까지이므로 모든 경우의 수를 다 확인하면 됩니다 ㅎㅎ (완전탐색!!) 다만, 주의할 점은 뱀으로 이동하면 100번까지 더 빨라..

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제: 케빈 베이컨의 수가 최소인 사람의 번호를 출력하라. 문제 이해하기!! 케빈 베이컨이라하면 그래프의 한 노드에서 다른 노드로 최소 몇번을 걸쳐야 거기로 갈 수 있는지를 구하면 되는 문제입니다. 즉, BFS를 쓰면 되는 문제라고 볼 수 있습니다. ※ 다만, DFS를 쓰면 틀리니 주의하세요! DFS를 쓰면 틀리는 이유는 깊이와 너비 우선 방식의 노드 접근법을 생..

처음에는 하.. 이걸 어떻게 풀어야 하나 생각했는데 보니까 N이 10개더라구요. 그래서 바로 브루트포스로 돌렸습니다!! ㅎㅎ 그러다가.. dfs로 돌리고 페일.. ㅠㅠ 그리고 bfs로 바꿔서 성공했습니다. (나중에 알았지만, dfs도 풀 수 있는데 하... 제가 다 만들어 놓은 코드에서 합계 계산을 잘 못 했더라구요 ㅠㅠ 까빙..) 풀이 방법은 각각의 N-a와 a개의 도시 조합을 나누어서 브루트포스를 돌리면 됩니다. dfs / bfs 방법 둘 다 가능한데, bfs가 쉽습니다... ㅎㅎ bfs 추천 드릴게요! 코드: from itertools import combinations def bfs_com(x, cnt): global res1 Q = connect.get(x)[:] while Q: tmpp = Q..

백준 문제 주소: www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제가 귀여워서 시작했습니다. ㅎㅎ 푼 방법은!!! 아기상어의 위치는 움직이므로 처음 시작점을 9 -> 0으로 만듭니다. BFS를 이용하여 가장 가까우면서 먹을 수 있는 물고기를 찾아 잡아먹고! visited 배열을 만들어 자기 자신이 갔던 곳을 체크하면 됩니다. 한 번 잡아 먹을 때마다 계속 visited 초기화와 지난 시간을 체크하고, BFS 큐를 초기화하여 잡아 먹은 지점에서 ..

백준 문제 주소 : www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net DFS, BFS의 머나먼 조상님 미로 문제에 조건 한 가지를 추가한 문제였습니다. 미로에서 단 한번!!! 벽을 부술 수 있다는 건데요. 하 ㅠㅠ 너무 힘들었어요 보이나요 제 노력... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 처음은 그냥 itertools 라이브러리의 combinations을 사용해서 1이 하나씩 사라진 모든 2차원 배열을 만들었습니다. 바로 메모리초과~~^^ 그래..