Algorithm/graph

1. 문제 설명 링크 : https://www.acmicpc.net/problem/11672. 풀이과정문제 해결의 흐름  트리에서 임의의 두 점 사이의 거리에 대하여 가장 긴 거리를 찾는 문제이기에 임의의 두 점 사이의 거리를 모두 구해 가장 긴 거리를 찾는 방법을 떠올렸습니다. 즉, 완전탐색과 BFS를 결합하여 문제를 풀고자 하였습니다. 하지만 아래와 같은 트리 구조를 예로 들어봤을 때, 굳이 완전탐색을 적용하여 모든 점을 탐색할 필요 없이 더 간단하게 풀 수 있는 방법이 있지 않을까 고민했습니다. 1 / \ 2 3 / \ 4 5 \ 6    3. BFS는 특정 노드에서 출발하여 모든 노드를 ..

1. 문제 설명문제 링크 : https://www.acmicpc.net/problem/31791부산대학교 2024 pnup div1 / div2 기출문제 2. 풀이 과정문제 해결의 흐름입력 받을 때 바이러스 위치들을 전부 queue에 저장하자bfs 구현 q_virus와 q_building, 둘 중 하나가 빌 때까지 bfs 탐색이 이루어진다.Tg의 시간동안 virus가 감염시키는 것이 building이 완전히 감염되는 것보다 우선시되어야 한다. virus의 상하좌우에 building이 위치해 있다면 해당 building은 감염되었기에 q_building에 push해주자virus의 상하좌우에 안전지역이 위치해 있다면 해당 안전지역은 감염되어 virus가 되었기에 q_viurs에 push해주자q_buildin..

1. 문제 설명링크 : https://www.acmicpc.net/problem/94662. 풀이 과정문제 해결의 흐름 백준 '2668 숫자고르기'와 비슷하다고 생각했는데 많이 다른 거 같다 ㅠㅠ...이 문제의 키포인트는 '사이클을 완성할 때까지 탐색하다가 사이클을 이루는 요소들 골라주기'이다.  사이클을 완성시키는 경우는 어떤 것이 있을까? 예를 들어 아래의 경우 1 -> 4 -> 7 -> 6 -> 4 와 같이 사이클을 형성한다. 1로 시작해서 4로 끝났는데 뭔 사이클이냐?라고 생각할 수도 있다. 하지만 4 -> 7 -> 6 -> 4의 사이클을 이룬다! 따라서 이와 같이 사이클을 이루는 경우 탐색을 멈추고 사이클을 이루는 숫자들을 백트래킹해주자! 12345674137346 나의 코드 #include #..

1. 문제 설명링크 : https://www.acmicpc.net/problem/19872. 풀이 과정문제 해결의 흐름 좌측 상단에서부터 시작해서 상하좌우로 탐색하며 이동할 수 있는 최대 칸 수를 구해야하는 문제이다.dfs를 이용해 최대 칸 수를 완전 탐색으로 구해보자.이때, 알파벳 개수는 26개이므로 26개의 인덱스를 갖는 int형 배열을 통해 방문처리해주자.나의 코드 #include using namespace std;int dr[4] = {0,0,1,-1};int dc[4] = {1,-1,0,0};int R, C;int result_cnt = 0;char alphabet_map[20][20]; // 대문자 알파벳들을 입력 받을 이차원 배열int visited[26] = {}; // 전부 0으로 초..

1. 문제 설명링크 : https://www.acmicpc.net/problem/1525  2. 풀이 과정문제 해결의 흐름 문자열의 형태로 입력 받는다. ex) "1034567" 이차원 배열을 bfs를 통해 탐색한다. (queue에 push되는 값 : 0의 위치값과 퍼즐 위치 정보를 담은 문자열)  퍼즐을 이동시킨 형태 자체가 갱신값이므로 문자열로 치환하여 방문 처리해주자.이동하여 특정 위치에 도달하는 문제 : 이동 위치가 갱신 값연산하여 특정 값을 만드는 문제 : 연산 결과가 갱신 값 방문처리되는 문자열의 정수값은 1억이다. 그렇기에 int형 배열에 2억 개의 값을 초기화시킨다면 메모리 초과가 발생하므로 해시맵을 사용하였다. 나의 코드 #include #include #include // 해시맵 사용..

1. 문제 설명링크 : https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때www.acmicpc.net2. 풀이 과정문제 해결의 흐름  일단 단순하게 구현해보자. 이동할 때마다 1씩 증가되는 현재 이동 시간, curTime값을 통해 현재 동생의 위치 cur_K의 값을 갱신해주자.  예제로 17 5의 입력이 들어왔을 때를 생각해보자. 동생의 위치를 찾는 과정을 다음과 같다. 이때, 이전에 풀었던 숨바꼭질 1~4의 방식대로 방문처리해준다면 15 ..

1. 문제 설명링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때www.acmicpc.net2. 풀이 과정문제 해결의 흐름  '1697 숨바꼭질' 문제와 같은 방법으로 최단 시간을 출력하자.⭐️ 최단 시간까지의 이동 과정은 어떻게 저장할 것인가?? memo라는 int형 배열을 만들어준 뒤 memo[next_position] = cur_position을 통해 현재 위치 값을 저장해 주자.  문제 조건을 만족하는 position이 re..

1. 문제 설명링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때www.acmicpc.net2. 풀이 과정문제 해결의 흐름 ⭐️ bfs를 통해 이 문제를 푼다면 문제의 핵심은 '어쨌든 연산 횟수가 가장 적은 경우가 최단 시간이 된다'이다. 예를 들어 입력이 1 17이라면 아래와 같이 2가지 경우가 가장 적은 연산 횟수로 동생의 위치에 도달할 수 있는 방법일 것이다. ⭐️따라서 순간이동하는 경우 시간 경과가 0초라고 하더라도 가장 적..