본문 바로가기

Algorithm/백준15

백준 1697 숨바꼭질 - C++ 접근 해당 문제는 BFS로 쉽게 접근할 수 있다. BFS나 DFS나 모든 정점을 1번만 방문하는 알고리즘인데 BFS는 간선의 가중치가 1이라는 조건일 때 최단 거리 구하는 문제에 응용할 수 있다. 문제에서 보면 어떤 정점 N에서 N-1, N+1, N*2의 정점에 도달하는데 걸리는 시간이 1이라고 한다. 여기서 시간 1은 정점과 정점을 연결하는 간선의 가중치가 될 수 있다. 문제는 다음과 같이 순차적을 처리 될 수 있다. 1. N과 K의 정점 입력 2. N을 큐에 푸쉬, N 방문 표시, N의 거리 표시 3. 큐가 빌 때까지 계속 돌기 4. 큐에서 한 정점을 빼서 이동 가능한 정점의 노드를 만든다. 5. 이동 가능 정점이 이동가능한 거리에 있는지 조건 확인 후 큐에 푸쉬, 방문 표시, 거리 표시를 한다. 6.. 2020. 9. 13.
백준 16947 서울 지하철 2호선 - C++ 접근 1. 순환선에 속하는 정점 파악 2. 순환선에 연결되어 있는 정점들의 최소거리를 구하기 순환선을 어떻게 구할지 부터 알아보면 다음과 같다. 순환선은 DFS를 이용하여 구할 수 있다. 먼저, 사이클을 형성하려면 최소 3개의 정점이 연결되어 있어야 한다. 그리고 1에서 시작한 정점이 다시 1로 돌아와 사이클을 형성하려면 3번의 이동이 필요하다. 사이클 형성 시 사이클에 속하지 않은 정점은 제외해주기 위해 사이클이 만들어질 때 시작 정점을 return값으로 주어야 한다. 예를 들어, 1 -> 2 -> 3 -> 1 탐색이 되었다고 하면 1 재방문시 이동거리가 3이어서 사이클이 형성된다. 그렇다면 return 하면서 cycle 기록을 해준다면 문제가 없다. 만일 4 -> 2 -> 1 -> 3 -> 2순으로 .. 2020. 9. 8.
백준 7562 나이트의 이동 - C++ 접근 나이트가 있는 위치 기준(x,y)으로 나이트가 이동할 수 있는 위치는 (x-1, y-2), (x-2, y-1), (x-2, y+1), (x-1, y+2), (x+1, y+2), (x+2, y+1), (x+2, y-1), (x+1, y-2) 이런식이다. 1. 주어진 x,y를 기점으로 갈 수 있는 곳에 표시를 한다. - bfs 탐색 알고리즘을 활용하여 똑같은 위치를 방문하지 않도록 한다. - 똑같은 위치는 0인지 아닌지로 판별한다.(0이면 아직 방문하지 않음) - 현재 위치에서 다음 위치로 이동할 때는 현재 위치 +1을 한다. 2. 계속 방문 하다가 현재 위치가 도착지 위치와 동일하면 얼마나 걸렸는지 출력 #include #include using namespace std; int A[301][301].. 2020. 7. 27.
백준 7576 토마토 - C++ 접근 입력이 주어졌을 때 익은 토마토를 전부 q에 넣고 bfs 탐색을 시작한다. 만약 아직 익지 않은 토마토가 있다면 출력은 -1 그렇지 않다면 모든 토마토가 익는데 걸린 시간 출력 #include #include using namespace std; int A[1001][1001]; int check[1001][1001]; int low[] = {-1, +1, 0, 0}; int col[] = {0, 0, -1, +1}; int M, N; int bfs(){ queue q; // 익은 토마토 찾아서 q에 넣기 for(int i=1; i M >> N; for(int i=1; i A[i][j]; } } int cnt = bfs(); for(int i=1; i 2020. 7. 27.

티스토리툴바