반례5 [C/C++] 백준 2206: 벽 부수고 이동하기 (BFS,tuple 이용 풀이) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 구현! 사실 원래의 BFS를 이용한 최단거리 알고리즘에서 조금만 추가하면 쉽게 풀 수 있는 문제이다. 여기서 중요한 것은 tuple안의 4개의 원소를 집어넣어 각각 x좌표, y좌표, 벽을 뚫고 지나갔는지에 대한 여부, 현재까지의 거리를 저장해야 하는 것이다. 또한 중요한 것이 visit 배열인데 기존의 2차원으로만 표현하면 안되고 3차원으로 표현하여 벽을 뚫고 지나갔는지에.. 2023. 9. 18. [C/C++] 13549: 숨바꼭질 3 (BFS,Queue) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 결론부터 말하자면 이 문제는 queue를 이용해 bfs로 풀 수 있는데 이때 2의 배수일 때는 0초만에 도달 가능하다는 것만 유의하면 된다. 구현?? 이를 구현하기 위해서 내가 사용했던 방법은 함수 after_onesec와 after_zero이다. after_onesec는 1초뒤에 갈 수 있는 곳을 queue에 넣는 방식으로 동작되는데 이때 queue.fron.. 2023. 9. 12. [C/C++] 6064: 카잉 달력 일단 이 이중 반복문을 통하여 모든 m*n케이스를 찾아보려고 할 경우 제 시간안에 찾아볼 수 없다. 그렇기 때문에 특정 조건일 때만 돌아가도록 만들어줘야 한다. 이 문제는 결국 x+M*a=y+N*b 라는 a와 b에 관한 부정방정식을 푸는 것인데 결국 이는 답이 되는 수를 t라고 한다면 t%M==x t%N==y가 되도록 만들어줘야한다. 그렇기 때문에 while문에 들어가는 초기 변수가 j=x_target이 된 것이고 while문을 한번 돌때마다 x만큼 증가시켜주면서 만족하는 수가 있는지 확인해줘야한다. 한가지 유의해야할 점은 x==x_target && y==y_target일 때인데 사실 이 경우 x%x_target이 x가 아니라 0이므로 이때를 주의하여 코드를 작성해야한다. 또한 이 경우에는 gcd 유클리.. 2023. 8. 24. [C] 1004: 어린 왕자 일단 문제는 예전에 원의 방정식에서 배웠던 것 처럼 출발점과 도착점이 각각 원 안의 있냐 없냐로 최소의 행성계 진입/이탈 횟수가 정해진다. 따라서 출발지/도착지와 원의 중점 사이의 거리가 원의 반지름보다 작다면 안에 있다는 것을 알 수 있다. 여기서 주의해야할 점은 출발점과 도착점이 모두 한 원 안에 있을 수 있다는 것이다. 그래서 한 원 안에 있는 경우의 수도 뺴줘야하기 때문에 tmp1과 tmp2를 이용해 출발점과 도착점이 각각 원안에 있는지 확인한 후 두개의 합, 즉 tmp1+tmp2==1인 경우에만 cnt++를 해줌으로써 문제를 풀었다. 기억해야할 점 1. pow 함수와 sqrt 함수는 모두 double형 변수에 대해서만 연산이 가능하고 다른 연산을 할때도, 예를 들어 나눌때, 계산결과가 달라질 수.. 2023. 8. 8. 이전 1 2 다음
