맛있는감귤

문제 : 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/1726출처Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 고등부 3번 명령어 go K의 의미를 잘못 해석해서 해맸었는데 결론은 총 다섯 가지 방법을 탐색하면 됩니다go 1, go 2, go 3, 90도 회전 -90도 회전.가장 중요한 것은 visited배열의 활용, 예외사항 판별, 실행 가능한 명령어 구분입니다.1. 방향 구분없이 이동만 한다면 좌표에 해당되는 2차원 visited배열을 만들었겠지만 방향이 존재하기 때문에 방향에 따른 visited배열을 추가하여 3차원 배열 생성2. 맵 이탈, 재방문, 궤도가 아닌 곳을 예외처리3. go 1,2,3 / 90도, -90도 회전먼저, 좌표와 방향, 그리고 명령어 횟..

문제 : 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/9328출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 Preliminaries K번 생각보다 많이 삽질한 문제였다. 최소 경로를 구하는 것은 아니기 때문에 열쇠가 없는 문은 대기 큐에 넣어 놓고 열쇠를 구했을 때 다시 큐에 넣어주는 방식으로 해결했다. 만약 입력받을 때 요소를 구분한다면 순서가 중요하다. 왜냐하면 A와 a가 전부 테두리에 있을 수도 있기 때문이다. #include &ltiostream&gt #include &ltqueue&gt using namesp..

문제 : https://www.acmicpc.net/problem/1463 1차원 좌표에다가 증감이 아닌 감소만 하게 되는 연산이니 BFS로 풀 수 있을 것이라 판단하고 풀었다. #include &ltcstdio&gt #include &ltqueue&gt using namespace std; queue&ltint&gt 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&gt0 ..

문제 : 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 &ltiostream&gt #include &ltqueue&gt using namespace std; bool nextPrime(int n){ if( (n&1) == 0 ) return (n == 2); for(int i=3; i*i&lt=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..