728x90 C++49 [c++] 백준 숨바꼭질 4(13913), bfs, 반례모음 문제 https://www.acmicpc.net/problem/13913 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다. 반례모음 24 300 10 24 2.. 2023. 8. 18. [c++] 백준 말이 되고픈 원숭이(1600), bfs, 반례모음 문제 https://www.acmicpc.net/problem/1600 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x x 말 x x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포.. 2023. 8. 16. [c++] 백준 숨바꼭질 3(13549), bfs, 반례모음 문제 https://www.acmicpc.net/problem/13549 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 반례모음 10000 0 10000 2 7 1 1 17 1 4 6 1 0 1 1 0 3 2 0 0 0 1 32 0 3 22 1 5 7 2 1 10000 3 1.. 2023. 8. 16. [c++] 백준 다리 만들기(2146), BFS, 반례모음 문제 https://www.acmicpc.net/problem/2146 회색은 땅, 하얀색은 바다. 땅간의 연결 가능한 최단거리를 구하시오. 반례모음 5 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 2 5 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 6 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 5 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 2 4 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 4 풀이 풀이가 2가지 있습니다. 1) BFS기반 정석적인 풀이 - 땅의 영.. 2023. 8. 9. [c++] 백준 빙산(2573), BFS, 반례모음 문제 https://www.acmicpc.net/problem/2573 해마다 위의 그림처럼 빙산이 녹습니다. 숫자를 제외한 빈 공간은 모두 0(바다)으로, 1년이 지나면 인접한 빙산을 녹이는데, 0의 개수만큼 녹습니다. 처음 빙산이 분리될 때, 몇 년이 지났는지를 출력하시오 분리되지 않고 모든 빙산이 녹을 때는 0을 출력. 반례 5 5 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 4 4 0 0 0 0 0 3 1 0 0 1 3 0 0 0 0 0 1 5 7 0 0 0 0 0 0 0 0 3 3 2 3 3 0 0 4 0 4 0 3 0 0 0 0 0 4 3 0 0 0 0 0 0 0 0 0 5 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0.. 2023. 8. 7. [c++] 백준 텀프로젝트(9466), BFS, 반례추가 문제 https://www.acmicpc.net/problem/9466 팀을 이루지 못하는 학생 수 구하기. 팀을 이루는 조건 1 -> 3 -> 5 -> 1 : 자기 자신으로 돌아와야 함. 1 -> 1 : 혼자 팀 팀을 못 이루는 조건 1 -> 3 -> 5 -> 3 : 1은 팀 x 1 -> 3 -> 5 -> 5 : 1,3은 팀 x 풀이 위의 조건에서와 같이 현재 n에서 탐색을 할 때, 팀을 이루든 이루지 못하든 무조건 순환루프에 걸리게 되어 있습니다. 순환루프에 걸렸을 때, 팀을 이루는 사람과 이루지 못하는 사람을 분리해서 표시를 해주면 됩니다. n번째에서 표시를 마치고, n+1번째에서 탐색을 할 시, 1~n번째에서 표시한 사람을 가르킨다면 이 또한 팀을 이루지 못한다고 할 수 있습니다. 이미 앞에서는 .. 2023. 8. 1. [c++] 백준 벽 부수고 이동하기(2206), BFS 문제 https://www.acmicpc.net/problem/2206 NxM 형태의 맵에서, 0은 이동가능, 1은 벽으로 이동 불가. 상하좌우로만 이동가능. 좌측 상단(1,1)에서 우측하단(N,M)까지 이동 가능한 최단 거리 출력. 이동 불가시 -1 출력. 벽을 1 개만 부실 수 있음. 풀이 일반적으로 최단거리 출력은 방문여부 체크가 중요함. (map과 방문여부 체크하는 map_check를 따로 만듬) 이미 방문한 곳은 최단거리가 아니라고 가정하기 때문. 하지만, 이 문제는 벽을 1개 부실 수 있기 때문에 이미 방문한 곳이라도 벽을 부수고 방문했느냐 혹은 부수지 않고 방문 했느냐로 나뉘게 됩니다. 다시 말해, 방문여부 체크를 벽을 1개 부셨을 때와 부수지 않았을 때를 나누어서 생각해야 합니다. 따라서,.. 2023. 7. 29. [c++] Tuple 사용법 여러 자료형을 묶어서 사용할 수 있음. #include tuple t(1, 'a', "abcd"); pair는 2쌍까지만 가능하지만, tuple은 여러 쌍 가능. 그렇지만, 같은 자료형을 사용하는 것을 추천. 3쌍 이상 묶어야 할 때 사용. 예를 들어, 큐에 3차원 좌표를 쌓을 때. 1. Tuple 선언 및 초기화 2. Tuple 원소 접근 3. Tuple 원소분해 4. 두 개의 튜플 연결 5. Tuple swap 2023. 7. 28. [c++] 3차원 배열(백터) 선언 및 초기화 3차원 배열을 선언하는 2가지 방법에 대해서 소개합니다. 1. 기본 배열로 선언 및 초기화 2. vector를 이용한 선언 및 초기화 1. 기본 배열로 선언 및 초기화 fill(arr[i], arr[i] + column, value) : i번째 행마다 column까지의 원소에 value를 할당함 2. vector를 이용한 선언 및 초기화 (M,N,H) 형태의 3차원 벡터 생성함. vector안에 또 다른 벡터를 선언하고 이를 높이(H)만큼 선언 초기값은 0으로 할당되며, 원할시 값을 할당할 수 있음. fill()을 사용해서도 초기화가 가능하다. 함수로 넘길시 vector를 복사할 것인지, 주소만 넘길 것인지 생각해야 함. 벡터의 가장 큰 장점은 공간을 미리 할당하지 않아도 됨. 입력받은 공간 크기만큼 할.. 2023. 7. 27. [c++] 반복문 iterator처럼 사용하기. 2023. 7. 26. [c++] 백준 숨바꼭질(1679), BFS, 반례모음 문제 https://www.acmicpc.net/problem/1697 수빈이(N)이 동생(K)를 찾는 가장 빠른 시간 출력 수빈이는 현재 위치(X)에서 3가지 동작(X+1, X-1, 2*X) 가능 5 17 -> 4출력(5-10-9-18-17) 풀이 1차원에서 수빈이의 이동 가능한 모든 방향을 탐색, 동생을 찾을 때까지 계속한다. 마치 가능한 모든 경우의 수를 탐색하는 것과 같음. 1차원 벡터(배열)의 map을 만들고, 수빈이의 시작지점에 1의 값을 넣고, 다음 이동 배열 값에 현재 위치의 값+1을 해주며 확산한다. 동생을 찾을 시 종료. 예외 처리 - 이전에 방문한 좌표는 패스 - 배열의 일정 크기를 넘으면 패스 - 0 0을 받을시 0을 출력 - 기타 반례모음 아래에. 반례모음 입력 6 11 정답 (6.. 2023. 7. 26. [c++] 백준 불!(4179), BFS, 반례모음 문제 https://www.acmicpc.net/problem/4179 J와 F(불)이 미로에 있음. J는 F를 피해 미로를 빠져나와야 한다. 미로 밖으로 나오면 성공 #: 벽 .: 지나갈 수 있는 공간 J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간) F: 불이 난 공간 J가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다. J가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 풀이 맵에서의 J와 F의 좌표를 모두 큐에 쌓고, 하나씩 BFS를 이용해 인접한 좌표로 이동한다. 핵심은 조건문을 통한 예외처리가 아닐까 싶다. 특이사항 - 불이 여러개일 수 있음. - J가 벽에 갇힐 수도 있음. 맵을 문자열로 구성하고, J나 F가 이동시에 현재 좌표에.. 2023. 7. 26. 이전 1 2 3 4 5 다음 728x90
