tony9402

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

백준 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/..