맛있는감귤

문제 : https://www.acmicpc.net/problem/5214출처Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 4번 이 문제는 입력만 잘 받으면 BFS로 해도 시간초과가 나지 않는다.핵심은 임의의 열의 개수를 어떻게 vector에 push하느냐 이다.문제 테스트 케이스를 돌려보면1 : 10 11 2 : 10 3 : 10 12 4 : 11 5 : 11 13 6 : 12 13 14 7 : 12 13 8 : 14 9 : 14 10 : 1 2 3 11 : 1 4 5 12 : 3 6 7 13 : 5 6 7 14 : 6 8 9 가 나온다. 잘 활용해서 풀어보도록 하자. 12345678910111213141..

문제 : https://www.acmicpc.net/problem/14226간단한 BFS이지만 visited 배열을 잘 활용하지 못한다면 원하는 정답이 안나올 것이다.현재 글자수 뿐만아니라 클립보드에 저장 돼 있는 글자 수도 고려해줘야 한다.핵심 visited[글자수][클립보드]1234567891011121314151617181920212223242526272829303132333435363738394041#include #include using namespace std;int S,cnt=0;queue q;bool visited[2002][2002];int main(){ scanf("%d",&S); q.push(make_pair(1, 0)); visited[1][0]=1; while(!q.empty()..

문제 : https://www.acmicpc.net/problem/14442 벽 부수고 이동하기의 업그레이드 문제입니다.기존의 문제는 벽 부술 수 있는 기회가 한번뿐이지만 이 문제는 K번이라는 것 빼고는 같은 문제에요.visited배열을 3차원으로 만들어 visited[r][c][0 or 1 벽 부수기 스킬 사용 여부]를visited[r][c][k]로 관리해주면 그만입니다.입력이 뭉쳐서 나오니 잘 해결합시다. 저는 char 배열로 이어서 받았습니다.int형 배열로 받고 싶다면 반복 for문으로 scanf("%1d",&map[i][j]); 이런 식으로 받으면 되겠죠.그리고 이동이 1부터 시작하는 것도 유의하신다면 쉽게 AC받으실 수 있을거에요~코드의 이해 안되시는 부분은 댓글 남겨주시면 정성껏 답변 해드리..

문제 : https://www.acmicpc.net/problem/12761출처University > 전북대학교 > 2016 전북대 프로그래밍 경진대회 G번저는 문제를 잘못 이해해서 동규와 주미가 각 턴마다 움직인다는 줄 알았습니다.알고 보니 스카이 콩콩이 두개..여튼 문제 해결방법은 BFS를 이용해 각 시간마다 움직일 수 있는 거리를 다 Queue에 push하는 것 입니다. #include #include using namespace std; int A, B, N, M, ans = 0; bool visited[100002]; queue q; int main() { scanf("%d%d%d%d", &A, &B, &N, &M); q.push(N); visited[N] = 1; while (!q.empty(..

문제 : https://www.acmicpc.net/problem/2146제가 푼 방식에는 두 가지 핵심이 있습니다.먼저 각 섬의 모서리 부분을 찾고 각 모서리가 어느 섬의 것인지 구분하기 위한 라벨링 작업두 번째는 각 섬에 대한 모서리 간의 거리 비교입니다. 라벨링은 DFS로 돌면서 근처에 물이 있으면 vector에 삽입했습니다. 한 지점에서 주위에 물이 두 군데 이상이면 중복 삽입되기 때문에 flag를 이용해 제외시켜주었습니다. 거리 비교는 BFS로 하려다가 굳이 그럴 필요가 없을 것 같아 서로 다른 라벨을 가지고 있는 섬끼리 비교하며 그냥 좌표를 빼줬습니다. #include #include using namespace std; int map[102][102], no=2, N, ans=98765432..

문제 : https://www.acmicpc.net/problem/1463 1차원 좌표에다가 증감이 아닌 감소만 하게 되는 연산이니 BFS로 풀 수 있을 것이라 판단하고 풀었다. #include <cstdio> #include <queue> using namespace std; queue<int> q; bool visited[1000000]; int main(){ int N,cnt=0; scanf("%d",&N); q.push(N); while(!q.empty()){ int sz=q.size(); while(sz--){ int n = q.front(); q.pop(); if (n==1){ printf("%d\n",cnt); return 0; } if(n%3==0 && n/3>0 ..

문제 : https://www.acmicpc.net/problem/9019출처ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2011 D번횟수가 아닌 연산의 순서를 출력하는 BFS 문제.그냥 queue 으로 풀었다.100이라는 숫자가 L을 했을 때 1000이되어야하는지 1이 되어야하는지 헷갈려서 두 방식으로 다 풀어봤는데 1000이 되는게 맞았다.4636 MS 나온건 함정 #include #include #include using namespace std; int main(){ int T; cin>>T; while(T--)..

문제 : https://www.acmicpc.net/problem/5427출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 F번 일반적인 미로찾기에서 퍼져나가는 장애물이 추가된 문제다. 미로찾기 + 바이러스 라고 생각하면 된다.시간을 따로 관리했다면 3차원 배열로 풀었을텐데 일괄적으로 관리해서 2차원으로 해결했다.먼저 불이 번지는 것을 연산하고 이동을 했다. 어처피 현재 위치는 큐에 들어있기 때문에 불이 먼져 번져도 상관없음비슷한 문제 : https://www.acmicpc.net/problem/3055 #include #includ..

문제 : https://www.acmicpc.net/problem/1963출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 G번 최소 횟수를 구한다는 점에서 BFS를 이용해 풀 수 있다는 것을 유추할 수 있다. 이 문제의 핵심은 기존의 숫자를 한 자리씩 바꾸는 것과 소수판별이다. 제출횟수 대비 정답률이 굉장히 높은게 신기하다. #include <iostream> #include <queue> using namespace std; bool nextPrime(int n){ if( (n&1) == 0 ) return (n == 2); for(int i=3; i*i<=n; i++) { if(..

문제 : https://www.acmicpc.net/problem/5014출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2011 D번 1차원 BFS 문제, 주어진 U,D에 따라 상하 이동만 있다고 생각하면 된다. #include #include using namespace std; bool visited[1000001]; queue q; int main(){ int F,S,G,U,D,cnt=0; bool flag = false; cin>>F>>S>>G>>U>>D; visited[S]=true; q.push(S); while(!q.empty..