컴공과고씨

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 간단 정리 수빈이는 일직성 상에 n이라는 점에 있고 동생은 k라는 점에 있다. 수빈이는 걷거나 순간이동을 하는데 위치가 x일때 걷는다면 1초 후 x-1 or x+1로 이동하고 순간이동하면 0초 후 2*x 만큼 이동할 때 동생을 찾을 수 있는 가장 빠른 시간을 구해라. 문제 해결 방법 저는 bfs를 통해서 해결해 주었습니다. 수빈이의 점에서 일직성 상 범위 내..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 정리 1. 유저가 번호로 주어짐 2. 관계가 주어짐. 관계라는 것은 예를 들어 1 2 이렇게 주어지면 1과 2는 연결되어 있다는 것을 말함. 3. 관계가 1 2 주어지고 2 4 로 주어진다고 치면 1에서 4로 갈때의 단계는 1 2(1단계) 2 4(2단계) 그래서 총 2단계를 걸처 1에서 4가 연결되어 있다고 함. 이 때 다른 사람과의 관계의 총..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 간단 정리. 상어가 물고기를 먹으러 다님. 상어는 물고기의 크기보다 크면 물고기를 먹을 수 있음. 크기가 같다면 지나갈 수만 있음. -> 작으면 못지나 감. 물고기를 먹으면 그 칸은 빈칸이 됨. 상어가 한 크기에서 물고기를 먹은 횟수와 상어의 크기가 같게 되면 상어 크기가 1 증가함. 물고기를 먹을 때는 가장 작은 것을 우선으로 먹고 같은 크기가 많다면 가장 위쪽 우선 그 다음은 왼쪽..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 정리 바둑판 모양이 있음. 각 방 마다 지나갈 수 있는 방과 없는 방으로 나뉨. 갈수 없는 방은 뚫 수 있음. (0,0) 에서 (n-1,n-1)까지 가는데 방을 최소한으로 뚫어서 갈 때 몇 개를 뚫어야 하는가? 문제 해결 방법 BFS를 사용해서 탐색을 하는데 각 방 마다 뚫고 온 방의 개수를 적어서 BFS 탐색을 해주면 됩니다. 방의 초기 값은 크게 잡아 줍니다. 그 후 시작점은 0으로 해줍..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제를 읽어보면 탐색 문제인 것을 알 수 있습니다. BFS를 사용해서 풀었습니다. 전체적인 문제 해결 방법은 수빈이의 위치와 동생의 위치를 확인 후 같지 않다면 수빈이의 위치를 이동시킨 후 큐에 넣어줍니다. 큐가 빌 때까지 반복 해 주면 됩니다. 그러다 처음으로 위치가 같아지면 이제까지 걸린 시간을 저장해줍니다. 그 후 위치가 같고 그 전에 저장해둔 걸린 시간..

https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 문제를 읽고 bfs를 떠올렸다. 아이디어 백신 놓기 전과 결과를 비교한다. 여기서 만약 다른게 나오면 bfs를 돌려서 숫자를 결과의 값으로 바꾸어 주고 백신은 한번만 놓을 수 있기 때문에 비교를 멈춘다. 그 후 바뀐 값과 주어진 결과를 비교해서 하나라도 다른 값이 있다면 no를 다 똑같다면 yes를 출력해주면 된다. 단계별 풀이 1. 입력값 받을 두 개의..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제를 보고 bfs로 탐색을 하여 풀면 쉽게 풀릴거라고 생각해서 bfs로 풀어주었다. 풀고 난 후 힌트 부분쪽에는 다이나믹 프로그래밍이라고 되어있어서 다이나믹 프로그래밍으로도 풀고 두 개 방식 모두 정리해보았다. 첫번째 방식은 bfs로 푼 방식으로 처음에 딱 떠올라서 푼 방식이다. 입력 받은 n을 bfs에 넣어주면 bfs는 - 3으로 나눠지고 나눈수가 방문되어지지 않은 경우 큐에 넣어준다. - 2로 나눠지고 나눈수가 방문되어지지 않은 경우 큐에 넣어준다. - 1을 뺀 수가 방문되어지지 않은 경우 큐에 넣어준..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제를 보고 탐색으로 풀어야겠다고 생각했다면 바로 풀 수 있다. 한가지 조금 다른 문제와 다른거는 대각선으로 땅을 밟을 수 있기 때문에 대각선을 고려해야한다는 것만 주의해주면된다. 기존에 상하좌우를 dx[] = {0,0,-1,1} = dy[] = {1,-1,0,0} 이런식으로 4번을 반복해서 움직여주었다면 이번거는 dx[] = {0,0,-1,1, 1,1,-1,-1} = dy[] = {1,-1..

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 이 문제는 탐색 문제지만 고려해야할 것이 있다. 첫번째는 무조건 적인 탐색이 아니라 외부쪽에 있는 치즈를 전부다 방문하면 카운트 그 다음 안쪽에 있는 치즈 전부 탐색 후 카운트 이런식으로 순차적으로 가면서 카운팅을 해주어야 된다. 그래서 나는 bfs안에 기본적인 구조가 큐를 한번 쓰는 거라면 큐를 2번을 사용하여 구현을 해주었다. 일단 (0,0)에서 시작을 해서 탐색을 시작하여 1을 만났을 때는 temp큐에 넣어주고..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제 같은 경우 처음에는 계산 형식으로 고민을 하다 bfs를 써야겠다는 생각이 들었다. bfs를 쓰니 간단히 해결이 되었다. bfs 구성은 동생을 찾지 못하면 x+1, x-1, 2x를 visit에 넣어 방문했는지 검사한 후 방문을 하지 않았다면 각각을 q에 넣어주면 간단히 해결된다. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..