tony9402

백준 2178 미로탐색 이 문제는 (1,1)부터 시작해 (N,M)로 가는 길 중 가장 짧게 갈 수 있는 경로를 찾는 것이다. 최단 경로를 구하는 문제는 대부분 BFS로 푸는 문제이다. 따라서 이 문제도 BFS로 푸는 문제이다. BFS는 queue를 이용하는데 queue에서 pop할때 도착 지점의 좌표가 나올때까지 하면 된다.문제에 길은 무조건 있다고 하니깐 그냥 없을 경우를 생각하지 않고 계속 push하고 pop을 하면 된다. 1. pair가 있다는 걸 몰랐을 때 짠 소스(queue에 대해서 독학 했을 때...) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585..

오랜만에 에듀코포가 있어 해보게 되었다. 너무 오랜만이라 그런지 문제를 해석해야하는데 해석도 안되고 문제를 읽기도 싫어서 대충 예제를 보고 풀려고 했지만 A번은 1시간 동안 안 풀려서 B -> A -> C로 풀었더니 1시간이 훌쩍 지나가버렸다. A번은 두 문자의 차이가 2 또는 0(같은것)인것을 보면 되는 단순한 문제였는데 문제를 안읽어 제출을 많이 했다. B번은 대충 배열 쓰면 되겠지하고 봤더니 n의 범위가 최대 10^9여서 멍 때리다가 규칙을 찾고 대충 제출 했지만 케이스 n == 2일때만 틀려서 2일땐 그냥 노가다로 if문 떡칠을 하였다. C번은 처음에 O(n^2)로 풀었는데 TLE가 떠서 O(n) 풀이가 있을꺼 같아 살짝 그리디하게 짜봤더니 AC가 떳다. 시간 복잡도 A번 -> O(N)B번 -> ..

백준 2606 바이러스 이 문제는 (매우..?) 쉬운 문제이다. 알고리즘 분류에는 플로이드 와샬로 되어있는데 이건 단순히 DFS로 풀린다.입력 받는 데이터를 이용해 인접리스트를 만들고 컴퓨터 1번에서 DFS를 한 번 돌리면 답이 나온다. 1234567891011121314151617181920212223242526272829303132333435363738#include#include using namespace std; vector map;bool visit[101] = { false };int computer_num, ans = 0; void dfs(int x){ ans++; visit[x] = true; for (int k = 0; k

백준 10026 적록색약 이 문제는 DFS 또는 BFS로 풀 수 있는 문제지만 둘 중에 하나로 두 번 돌려야 되는 문제이다. (두가지 풀이로 쓰기 귀찮아서 BFS 풀이만 올리겠다.) 먼저 BFS로 한 바퀴 돌릴 때 G인 곳을 R로 바꾸면서(R을 G로 바꿔도 상관없다) 색상에 의해 몇 구역으로 나뉘는지 체크를 하고 또 다시 BFS로 한 바퀴 돌리면 풀리는 단순한 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include#include#include u..

백준 1012번 유기농 배추 이 문제는 백준 2667번 단지번호붙이기와 거의 같은 문제이다.단지번호붙이기와 다른점은 단지마다 넓이를 구해야하고, 유기농 배추는 단지의 갯수만 구하면 되는 문제이다. 1. BFS를 이용한 풀이 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include#include using namespace std; queue q;int dx[] = { -1,1,0,0 };int dy[] = { 0,0,-1,1 };int map[55][55] = { 0 }; int main(){ int T; int m, n, k; int x, y; int ans; ..

백준 2667번 단지번호 붙이기 이 문제는 BFS로 풀어도 되고 DFS로 풀어도 되는 문제이다. 아는 사람도 있을 것이고 모르는 사람도 있을 수도 있으니 입력부분에서 하나 집고 가자면 예제 입력 부분을 보면 0110100 이런식으로 숫자가 붙어서 들어오는데 scanf를 잘 사용하면 숫자 한개씩 입력 받게 가능하다. (어떤 사람은 이걸 몰라 문자열로 입력 받아 처리하는 경우가 있었다. 이 문제에선 큰 상관이 없긴 하지만 다른 문제에서 쓰일 때가 있을 것이다.) 1234567for(int i=0;i

다음 글 부터는 백준 DFS/BFS 관련 문제를 풀이 하는 글을 올릴 예정이다. 일단 백준에 있는 문제들 중에서 DFS/BFS 문제를 나열해보자 boj.kr/1260 - DFS와 BFSboj.kr/2178 - 미로 탐색boj.kr/7576 - 토마토(2차원)boj.kr/7569 - 토마토(3차원)boj.kr/2667 - 단지번호붙이기boj.kr/1012 - 유기농 배추boj.kr/2583 - 영역 구하기boj.kr/2468 - 안전 영역boj.kr/14502 - 연구소boj.kr/2589 - 보물섬boj.kr/10026 - 적록색약boj.kr/3055 - 탈출boj.kr/2206 - 벽 부수고 이동하기boj.kr/14442 - 벽 부수고 이동하기 2boj.kr/1600 - 말이 되고픈 원숭이boj.kr/..

간선 정보를 저장할 때는 두가지를 이용하여 저장할 수 있다. 1. 인접행렬 공간 복잡도 O(V^2) 간선 유무 확인 시간 O(1) 2. 인접리스트 공간 복잡도 O(V+E) 간선 유무 확인 시간 O(1) (x) - BFS는 현재 정점에서 가장 가까운 곳부터 차례대로 탐색을 해나가는 너비우선탐색 Queue를 사용 기준점으로부터 가까운 곳부터 간다. 최적의 해를 구하라 - DFS는 현재 정점부터 갈 수 있는 곳까지 파고 들어 탐색하는 깊이우선탐색 Stack(또는 재귀)을 이용 백트레킹에 유리 DFS/BFS를 사용하면서 조심해야할 것 : 이미 방문한 정점에 다시 갈 수 있으니 visited 배열을 만들어 체크해야한다.

STL은 Standard Template Library의 약자이며 Problem Solving에 편리하게 쓰이는 템플릿이다. 1. find find함수는 algorithm 헤더 파일에 있다. find함수의 생김새는 find(iterator first, iterator last, const T& val) 이와 같다. 간략히 설명을 하면 찾고차 하는 값을 Linear하게 검색하여 그 값이 존재하면 위치를 가리키는 iterator를 반환하고 값이 존재하지 않으면 end()를 반환한다. 시간복잡도 : O(n) 2. sort sort함수는 find와 마찬가지로 algorithm 헤더파일에 존재한다. sort는 두가지로 정의되어있다. - sort(iterator begin, iterator end) - sort(i..