Algorithm/graph

1. 문제 설명링크 : https://www.acmicpc.net/problem/10122. 풀이과정문제 해결의 흐름 문제를 살펴보면, 배추가 심어진 위치값들이 주어지고 서로 연결된 배추들이 하나의 집합(덩어리)를 형성함을 알 수 있습니다. 따라서 이 문제는 bfs를 통해 그래프에서 연결된 요소들의 개수를 찾아내는 문제임을 파악하였습니다. 입력값을 저장하기 위해 배추 밭은 저장하는 2차원 벡터(graph), 방문 여부를 체크하는 2차원 벡터(visited)를 사용하였습니다. 그러나 테스트케이스마다 graph와 visited를 초기화해야 하므로 다음 2가지 방법 중 하나를 사용할 수 있었습니다.전역 변수 2차원 벡터를 선언하고 assign()을 활용하여 크기를 재할당한다.테스트케이스마다 새로운 지역 변수로..

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..