알고리즘/백준 알고리즘

[백준 2606] 바이러스

글에 개요 백준 알고리즘 2606번 "바이러스" 문제입니다.해당 문제는 Union-Find 알고리즘을 활용하면 쉽게 푸실 수 있습니다. 또한 BFS/DFS 방식 모두로 풀 수 있습니다.저는 일단 Union-Find를 활용한 풀이와 BFS를 활용한 풀이 두 가지로 풀겠습니다. 앞서 다루었던, 아래 참고할 글 1번에 정리한 유니온 파인드 (Union-Find) 내용을 보시면 좋을 것 같습니다. [백준 2606] 바이러스: https://www.acmicpc.net/problem/2606 참고할 글http://brenden.tistory.com/33 ([알고리즘] 유니온 파인드(Union-Find) 정리글)http://brenden.tistory.com/34 ([백준 1717] 집합의 표현 정리글)핵심 내용초..

2018. 4. 25. 10:48

알고리즘/백준 알고리즘

[백준 14503] 로봇 청소기

글에 개요 백준 알고리즘 14503번 "로봇 청소기" 문제입니다.삼성 SW 역량 테스트의 기출 문제입니다.[백준 14503] 연구소 : https://www.acmicpc.net/problem/14503 참고할 글[완전탐색] : http://brenden.tistory.com/10[DFS] : http://brenden.tistory.com/13[BFS] : http://brenden.tistory.com/14핵심 내용해당 조건에 맞게 풀면 되는 문제 (BFS를 활용 가능)조건을 걸어주는 부분을 신경써야 된다.좌표를 신경써서 설정해 줘야 문제 풀 때 쉽습니다.해결 방법visited 배열에 로봇이 청소한 구역을 표시하기 위한 변수 설정을 한다.조건 1~ 4번 순서대로 작성한다.방향 관련 함수를 만들어 준다..

2018. 4. 14. 19:57

알고리즘/백준 알고리즘

[백준 14502] 연구소

글에 개요 백준 알고리즘 14502번 "연구소" 문제입니다.삼성 SW 역량 테스트의 기출 문제입니다.[백준 14502] 연구소 : https://www.acmicpc.net/problem/14502 참고할 글[완전탐색] : http://brenden.tistory.com/10[DFS] : http://brenden.tistory.com/13[BFS] : http://brenden.tistory.com/14핵심 내용DFS + BFS를 활용한 문제시간이 오래걸렸던 부분은 바이러스를 찾을 때 새로운 배열에 map[][]을 옮기는 작업을 해야된다.map을 옮기는 작업을 안해줬을 때는(map[][]에 바이러스 퍼짐까지 표시했을 경우) 되돌려주는 작업을 추가해야된다!!map을 복사하는 과정에서 virusMap[][..

2018. 4. 14. 16:38

알고리즘/알고리즘 개념

[알고리즘] 너비 우선 탐색 (Breadth-first search, BFS)

너비 우선 탐색(Breadth-first search, BFS) ① 너비 우선 탐색이란? ▷ 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘입니다.▷ 프림의 최소 스패닝 트리 알고리즘 등이 너비 우선 탐색을 골격으로 하고 있습니다. ▷ 위의 그림을 너비 우선 탐색을 사용하면 H0(단계) -》 H1(단계) -》H2(단계) 순으로 방문합니다.▷ k단계에 방문하는 정점들은 시작점으로부터 최단거리가 k입니다. (H0(단계) : 0단계, H1(단계) : 1단계, H2(단계) : 2단계)▷ 최단거리는 이동하는 데 필요한 최소 개수의 간선으로 보면됩니다.▷ 각 정점을 방문할 때마다 모든 인접 정점들을 검사합니다. 이 중 처음 보는 정점을 발견하면 방문 예정이라고 기록해 둔 뒤, 모든 인접 정점을 검사한 후..

2018. 4. 12. 21:42