알고리즘/문제풀이 - 백준

백준 1504 특정한 최단 경로

문제 : https://www.acmicpc.net/problem/1504 서론 우선순위 큐를 이용한 다익스트라 알고리즘으로 풀이했다. 아이디어 다익스트라 알고리즘은 1 -> 2 -> 3-> 4가 최단경로일때 1에서 4까지의 최단경로는 1~2까지의 최단경로를 포함하고 2~3까지의 최단경로를 포함한다. 즉 목적지까지의 최단경로는 중간지점들의 최단경로 합이다. 두개의 정점이 n1, n2일때 시작정점부터 두개의 정점을 거쳐서 종료정점까지 가는 방법은 1. 시작정점 -> n1 -> n2 -> 종료정점 2. 시작정점 -> n2 -> n1 -> 종료정점 두개의 방법이 있다. 1번 방법은 시작정점 -> n1의 최단경로, n1 -> n2의 최단경로, n2 -> 종료정점의 최단경로의 합을 구하면 되고 2번 방법도 마찬가..

2019. 6. 27. 20:01
알고리즘/문제풀이 - 백준

백준 1753 최단경로

문제 : https://www.acmicpc.net/problem/1753 서론 다익스트라 방법으로 풀이했으나 시간초과. 이후 우선순위 큐를 이용한 다익스트라로 해결. 아이디어 다익스트라 알고리즘은 1 -> 2 -> 3-> 4 그래프에서 1번에서 4번까지의 최단경로는 1번에서 2번, 2번에서 3번, 3번에서 4번까지의 최단경로를 포함한다는것을 전제로한다. 즉 최단경로 + 최단경로 = 최단경로다. 정점을 이동할때마다 최단경로를 계속 누적시켜주면 된다. 여기에 우선순위큐를 이용하게 되면 경로 중 최단경로를 우선적으로 탐색하여 탐색횟수를 줄일 수 있다. 구현 우선순위 큐를 이용한 성공한 구현 // c++ #pragma warning (disable : 4996) #include #include #include..

2019. 6. 27. 17:17
알고리즘/문제풀이 - 백준

백준 2667 단지번호붙이기

문제 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 서론 BFS를 이용하여 풀이 아이디어 좌표 (1,1)부터 (n,n)까지 모든 좌표에서 1이고 방문하지 않았으면 BFS를 실행 만약 단지 결과가 3개라면 BFS는 3번 실행되게 된다. BFS에서는 이동가능한 좌표 한칸씩 이동할때마다 집을 +1하고 방문처리 BFS에서 나올때 카운트된 집을 리턴하고 하나의 단지가 완성된다. 카운트된 집은 배열에 집어넣고 모든 집을 방문했으면 배열을 오름차순 정..

2019. 6. 26. 23:09
알고리즘/문제풀이 - 백준

백준 2806 바이러스

문제 : https://www.acmicpc.net/problem/2606 서론 그래프와 BFS에 대한 이해가 필요하다. 아이디어 1. vector로 그래프를 만든다. 2. 1번 컴퓨터를 큐에 넣는다. 3. 큐에서 컴퓨터 하나를 가져오고, 가져온 컴퓨터와 연결된 컴퓨터들 중 방문하지 않은 컴퓨터들을 방문처리하고 큐에 넣는다. 방문처리할때 감염된 컴퓨터 개수를 +1시킨다. 4. 큐가 비어있을 때까지 3번을 반복한다. 5. 감염된 컴퓨터 개수를 출력한다. 구현 vector 개수를 100으로 만들면 런타임에러가 발생한다. 100번 컴퓨터를 참조하기 위해서는 0~100까지 101개를 만들어줘야한다. // c++ #include #include #include using namespace std; queueq; ..

2019. 6. 26. 21:59
알고리즘/문제풀이 - 백준

백준 2178 미로 탐색

문제 : https://www.acmicpc.net/problem/2178 서론 https://hydroponicglass.tistory.com/14 과 같은 방식으로 이동횟수를 확인하고 방문하면 지도를 이동할 수 없는 0으로 갱신하는식으로 구현했는데, 시간초과가 발생했고 반복문의 종료조건에 반례가 있어서 무한루프가 발생됨을 확인. 수정하면 또다른 반례가 생길것 같아서 방문지 확인 배열을 만들었다. 이 방법이 깔끔하고 편한것 같다. 아이디어 입력이 라인단위로 되어있어서 라인을 숫자 하나씩 분할해야한다. string 자료형으로 라인을 입력받으면 배열 한칸에 한 글자씩 들어가는데, char로 된 배열 칸마다 int로 바꿔서 map에 넣으면 된다. 숫자 char를 int로 바꾸는 방법은 글자 '0'을 빼주면 ..

2019. 6. 26. 20:58
알고리즘/문제풀이 - 백준

백준 7569 토마토

문제 : https://www.acmicpc.net/problem/7569 서론 7576문제에서 z축이 추가된 문제. 풀이 BFS를 사용하는 7576과 아이디어는 동일 https://hydroponicglass.tistory.com/14 백준 7576 토마토 문제 : https://www.acmicpc.net/problem/7576 DFS/BFS 문제가 나오면 항상 DFS로 접근하는 습관이 있어서 BFS로 탐색문제 몇개를 풀어보려고 한다. 아이디어 BFS를 풀이하는 일반적인 방식을 이용 1. 토마토 행렬.. hydroponicglass.tistory.com 구현 7576문제와 달리 좌표변수가 3개(x,y,z)인지라 pair를 사용할 수 없게 되었다. 그래서 좌표를 pair가 아닌 구조체로 변경하여 큐에 ..

2019. 6. 26. 16:17