https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net BFS 응용 pair 로 좌표를 관리해줘도 되는데, 나는 그냥 편의상 x*1000+y 로 묶어서 1차원 배열로 만들어서 BFS를 돌려주었다. 불을 켜는 경우와 실제로 탐색하는 경우를 분리해줘야 하는데, 이를 위해서 방문체크를 위한 vis배열과 불이 켜져있는지 체크를 위한 light 배열 두개를 만들어서 각각 관리해줬다. 프로그램 작성 과정에서도..
https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 간단한 그래프 탐색 문제. BFS 알고리즘의 구현에 대해서 묻고 있다. 클래스3 문제에 해당한다. 굳이 신경써줄 점이라면 입력으로 받은 지도를 잘 저장하고 있다가 숫자를 출력할때 원래 갈수 있는 땅인데 고립/격리되어있어서 가지 못한 땅인지 원래부터 갈수 없는 땅인지 둘을 구분할때 사용해야 한다. 이런 2차원 격자를 탐색할때 int dx[] = {1,-1..
DP + BFS 문제. https://www.acmicpc.net/problem/16397 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net dp[k] 를 숫자 $K$를 만드는데 필요한 최소한의 버튼 누름 횟수 라고 하고, 숫자 $K$인 상태에서 두 버튼을 눌렀을때 변화하는 수를 각각 $A(K)$, $B(K)$ 이라고 하면 dp[A(K)] = dp[k] + 1 dp[B(K)] = dp[k] + 1 이 된다. 버튼 A, B를 누를 때 각각 숫자가 99,999..
제목이 같은 날먹문제... 트리에 존재하는 모든 경로 중 가장 긴것의 길이를 찾으라하고 있다. dfs로 풀었다. 일단 가장 긴 경로는 반드시 리프노드 - 리프노드 간 길이일 것이다. 리프노드가 아닌 노드가 긴 경로가 된다면 그 노드의 자식노드로 더 긴 경로가 있을수밖에 없기 때문이다 ( 가중치의 길이가 음수가 될 수 없다 ) 처음 생각한것은 1을 기준으로 가장 긴 경로 & 두번째로 긴 경로 를 찾는 것인데, 중복문제도 있고, 그림에서처럼 1을 지나지 않는 가장 긴 경로도 있기에 일단 루트노드에서 가장 긴 경로를 찾고, 그 경로에서 나온 리프노드를 시작점으로하는 가장 긴 경로를 찾아주었다. 루트노드에서 가장 긴 경로와 실제 가장 긴 경로가 1 ) 하나도 겹치지 않는다면 조건에 모순이 생기고, 2 ) 겹친다..
간선을 생으로 구현하면 MLE가 나오는 문제 간선의 갯수를 줄이기 위해서는 더미노드를 만들어서 하이퍼 튜브가 문어발 같은 느낌으로 펼쳐지게 설계해주면 된다. 그러면 모든 노드를 최소한의 간선만 가지고( 정점을 하나 더 써서 ) 이어줄 수 있고, 테스트케이스의 정답을 더미노드를 사용해서 문제를 해결하면 1 K 3 K 6 K 9 가 되는데, 정답, 즉 4를 N이라 하면 더미노드 K의 갯수는 N-1개 이다. 따라서 실제 정답은 우리가 bfs를 통해 구해준 가중치를 K로 두었을때 (K+1)/2를 출력해주면 답이 된다. 메모리 아끼는 팁으로는 가중치를 vis배열이랑 같이 묶어서 한번에 저장해줄 수 있다는 정도? 위의 더미노드를 만든다는 생각에만 도달하면 쉽게 AC를 받을 수 있다. 더보기 #include usin..
기본적인 BFS 문제 bfs만 짜면 AC받을수 있다. www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net #include #include #include using namespace std; vector v[123]; queue q; int visit[123] = {0}; void bfs(){ while(!q.empty()){ int node = q.front(); q.pop(); for(int i=0; i