본문 바로가기

그래프

 (22)
[C++/BOJ] 2468 : 안전 영역 (bfs/dfs) https://www.acmicpc.net/problem/2468 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3..
[C++/PGS] Lv.5 : 방의 개수 (그래프) https://school.programmers.co.kr/learn/courses/30/lessons/49190?language=cpp 문제 설명 원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다. ex) 1일때는 오른쪽 위로 이동 그림을 그릴 때, 사방이 막히면 방하나로 샙니다. 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요. 제한사항 배열 arrows의 크기는 1 이상 100,000 이하 입니다. arrows의 원소는 0 이상 7 이하 입니다. 방은 다른 방으로 둘러 싸여질 수 있습니다. 구현 자체는 어렵지 않다. 다만 한번 방문했던 노드를 다른 경로에서 다시 방문하게 되면 방이 만들어..
[알고리즘] 그래프 - 최단거리 구하기(cpp) N개의 노드와 M개의 에지가 있는 그래프에서, 세 노드 s, a, t가 주어졌을 때 s에서 a를 반드시 지나서 t까지 도달하는 가장 짧은 거리를 구하는 프로그램을 작성하시오. 입력 표준 입력으로 입력을 받는다. 첫 줄에는 노드의 개수 N과 에지의 개수 M이 주어진다. 노드의 개수는 3 이상 100 이하이고, 에지의 개수는 0개 이상 N(N-1)개 이하이다. 두번째 줄에는 세 정수 s a t가 주어진다. 노드들은 0 이상 N 미만인 정수들로 표현되며, 이 세정수는 각각 시작 노드, 중간 노드, 도착 노드를 나타낸다. 세번째 줄부터 총 M줄에 에지 정보가 주어진다. 한 줄은 에지 하나에 대한 정보를 나타내며, 세 정수 U V W로 이루어진다. U는 에지의 시작 노드, V는 에지의 도착 노드, W는 에지의 가..
[C++/BOJ] 10971 : 외판원 순회 2 (완전탐색, dfs, Backtracking) https://www.acmicpc.net/problem/10971 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가..
[C++/PGS] Lv.3 : 순위 (그래프/Floyd-Warshall) https://school.programmers.co.kr/learn/courses/30/lessons/49191# 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 선수의 수는 1명 이상 100명 이하입니다. 경기 ..
[C++/PGS] Lv.3 : 가장 먼 노드 (그래프/bfs) https://school.programmers.co.kr/learn/courses/30/lessons/49189 문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. ver..
[C++/BOJ] 1697 : 숨바꼭질 (BFS) 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 힌트 수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾..
[C++/PGS] Lv.3 : 네트워크 (DFS/BFS) 깊이/너비 우선 탐색(DFS/BFS) : 네트워크 문제 출처 - 프로그래머스 코딩테스트 고득점 Kit 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터..
728x90

티스토리툴바