DFS
-
백준 17142번 연구소 3 :: 마이구미알고리즘 풀이/그래프 2019. 6. 3. 20:31
이 글은 백준 알고리즘 문제 17142번 "연구소 3" 를 풀이한다. 삼성 SW 역량 테스트 문제이다. 문제 해결을 위해 DFS, BFS 2가지 모두 요구한다. 문제 링크 - https://www.acmicpc.net/problem/17142 DFS, BFS - https://mygumi.tistory.com/102 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 모두 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며,..
-
백준 1325번 효율적인 해킹 :: 마이구미알고리즘 풀이/그래프 2018. 11. 21. 00:44
이 글은 백준 알고리즘 문제 1325번 "효율적인 해킹" 을 풀이한다.문제는 DFS 를 통해 접근한다.DFS 가 익숙하지 않는다면, 아래 관련 링크를 읽어보면 좋다.문제 링크 - https://www.acmicpc.net/problem/1325DFS - http://mygumi.tistory.com/102- 현재 코드(Java)는 최근 재채점으로 인해 시간초과를 발생시킨다 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할..
-
백준 1799번 비숍 :: 마이구미알고리즘 풀이/그래프 2018. 1. 29. 20:16
이 글은 백준 알고리즘 문제 1799번 "비숍" 을 풀이한다.정올 문제로써, 풀이 방법은 DFS 를 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/1799DFS - http://mygumi.tistory.com/102 서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있..
-
백준 11559번 Puyo Puyo :: 마이구미알고리즘 풀이/그래프 2017. 12. 11. 11:10
이 글은 백준 알고리즘 문제 11559번 "Puyo Puyo" 를 풀이한다.시뮬레이션 문제로써, 시나리오를 정확히 이해한 후 그대로 구현하면 된다.본인은 그 과정속에 DFS를 통해 해결했다.문제 링크 - https://www.acmicpc.net/problem/11559 뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이..
-
백준 14889번 스타트와 링크 :: 마이구미알고리즘 풀이/그래프 2017. 10. 29. 14:42
이 글은 백준 알고리즘 문제 14889번 "스타트와 링크" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.본인은 DFS를 활용해 문제를 해결했다.문제 링크 - https://www.acmicpc.net/problem/14499DFS 참고관련 문제 - http://mygumi.tistory.com/191DFS 이해 - http://mygumi.tistory.com/102 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 ..
-
백준 14888번 연산자 끼워넣기 :: 마이구미알고리즘 풀이/그래프 2017. 10. 29. 00:12
이 글은 백준 알고리즘 문제 14888번 "연산자 끼워넣기" 를 풀이한다.2017 삼성 SW 역량 테스트의 문제 중 하나이다.본인은 DFS로 문제를 풀이할 것이다.문제 링크 - https://www.acmicpc.net/problem/14499DFS 참고관련 문제 - http://mygumi.tistory.com/191 DFS 이해 - http://mygumi.tistory.com/102 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이 때, 주어진 수의 순서를 ..
-
백준 1520번 내리막 길 :: 마이구미알고리즘 풀이/동적계획법 2017. 10. 12. 09:35
이 글은 백준 알고리즘 문제 1520번 "내리막 길" 을 풀이한다.풀이 방법은 DFS + DP(동적계획법) 을 통해 해결한다.DFS - http://mygumi.tistory.com/1021520번 - https://www.acmicpc.net/problem/1520 단순히 모든 경로를 탐색한다면, 시간 초과를 경험하게 된다.시간을 줄일 수 있는 방법은 다음과 같다.20 지점에 오면 더이상 탐색할 필요가 없이 경로가 존재한다는 것을 찾을 수 있다.존재하는 경로를 활용하는 방법으로써, 동적계획법을 이용할 수 있다. dp[y][x] = (y, x) 지점일 때 존재하는 경로의 갯수 DFS를 완벽히 이해하고 있다면, 쉽게 코드를 이해할 수 있다.* dp배열을 -1로 초기화한 이유는 방문여부를 위함이다. 1234..
-
백준 2251번 물통 :: 마이구미알고리즘 풀이/그래프 2017. 10. 3. 23:04
이 글은 백준 알고리즘 문제 2251번 "물통" 을 풀이한다.BFS 또는 DFS를 통해 문제를 해결할 수 있다.본인은 DFS로 풀이하겠다. (BFS가 좀 더 효율적이다)2251번 - https://www.acmicpc.net/problem/2251 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이 때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번..