본문 바로가기

Algorithm Problems/그래프

 (50)
[백준/C++] 1504번: 특정한 최단 경로 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 요약 1번 정점부터 N번 정점까지 존재하는 방향성이 없는 그래프가 주어졌을 때, 1번 정점에서 N번 정점으로 최단 거리를 출력한다. 단, 임의로 주어진 두 정점을 반드시 통과해야 한다. 한 번 이동했던 정점 또는 간선을 다시 이동할 수 있다. 코드 #include #include #include #include #include #include..
[백준/C++] 1967번: 트리의 지름 문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 요약 가중치가 있는 트리가 주어졌을 때, 트리의 지름을 출력한다. 트리의 지름이란, 트리에 존재하는 모든 경로들 중 가장 긴 것의 길이이다. 코드 #include #include #include #include #define MAX_N 500000 using namespace std; int n; bool visited[MAX_N + 1]; vector edges[M..
[백준/C++] 1261번: 알고스팟 문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 요약 N × M 크기의 미로에서 (1, 1)에서 출발해 (N, M)까지 가기 위해 벽을 최소 몇 개 부수어야하는지 출력한다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 코드 #include #include #include #include using namespace std; #define MAX 100 int n, m; int board[MAX..
[백준/C++] 14267번: 회사 문화 1 문제 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제 요약 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬한다. 즉, 상사가 한 직속 부하를 칭찬하면, 그 부하의 모든 부하들이 칭찬을 받는다. 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다. 직원들의 직속 부하관계와, 칭찬 정보가 주어질 때, 각자 칭찬 받은 수치를 출력한다. 코드 #include #includ..
[백준/C++] 4963번: 섬의 개수 문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 요약 정사각형으로 이루어져 있는 섬과 바다 지도가 주어졌을 때, 섬의 개수를 출력한다. 한 정사각형과 가로, 세로, 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 코드 #include #include using namespace std; // board는 ..
[백준/Python] 24230번: 트리 색칠하기 문제 https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 문제 요약 정점이 n개인 트리가 있다. 정점에는 1부터 n까지 번호가 붙어있고, 트리의 루트는 항상 1번 정점이며, 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다. + 색은 섞이지 않고 색칠할 때마다 그 색으로 덮어진다. (단, 하얀색으로 색칠할 수는 없다.) 트리의 정보(연결된 정점)와 색칠..

티스토리툴바