몽셀통통의 블로그

문제https://www.acmicpc.net/problem/2206 풀이최단 거리를 구하는 것 이므로 bfs 사용큐는 모두 3개가 필요한데 (x좌표, y좌표, 벽을 부순 횟수( 최대 1회 가능)) 이 세가지다bfs를 이동하면서 상하좌우 방향으로 이동하는데 상하좌우 뿐만아니라 다음 이동하는 원소가 1일 경우 벽을 부순 횟수를 1로 변경하여 계속해 나간다 중요한점은 visit[MAX][MAX][2]로 설정해야 한다.visit에서 벽을 하나도 안부순 경우(0)와 벽을 이미 부수고 지나간 경우(1)를 체크해 준다 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include..

문제https://www.acmicpc.net/problem/7569 풀이전형적이고 간단한 bfs 문제상하좌우 뿐만아니라 앞뒤까지 포함하여 총 6방향으로 bfs로 돌리면된다큐를 시작하면서 모든 토마토가 익었다면 return 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include#includeusing namespace std; int M,N,H,ans;int arr[101][101][101];int visit[101][101][101];int dir[6][3]={{-1,0,0},{1,0,0},{0,-1,0},{0,0,1},{0,1,0..

문제https://www.acmicpc.net/problem/1018 풀이dfs를 이용체스판이 8X8이므로 이 체스판의 첫번째 위치만 for문으로 dfs를 돌린다첫번째가 B나 W로 시작하게 각각 돌려준다간단한 dfs 코드1234567891011121314151617181920212223242526272829303132333435363738#include using namespace std; int N, M,ans=10000000;char arr[51][51]; void dfs(int n, int m,int x, int y, char cha,int cnt) { if (y == m) { y = m-8; x += 1; if (x == n) { ans = ans > N >> M; for (int i = 0; i..

문제https://www.acmicpc.net/problem/2931 풀이이 문제는 dfs를 이용하여 visit으로 체크하면서 이동하는 방법을 사용1. dfs를 이용하여 상하좌우 방향으로 이동 + visit으로 체크 (다시 0으로 만들지 않음)1-1. 상하좌우 방향으로 이동할 때 checkdir 함수 (현재 가스관 모양으로 움직이게 도와주는 함수)를 만들어서 가능한 반향으로만 이동2. 이동한 칸이 '.' 이면 원래 가스관이 존재 했던 곳이라 판단2-1. 비트마스크를 사용하여 bit 변수에 이동 방향을 변수에 저장3. '.'이면서 visit이 체크 된 곳의 좌표를 출력하고 bit에 맞는 가스관 모양 출력 이렇게 설정을하여 비트마스크에 적용 위와 같이 비트마스크 진행 코드12345678910111213141..

문제https://www.acmicpc.net/problem/9328 풀이bfs + 시뮬 문제1. 경계면에 있는 '.'이나 '$', 소문자가 있다면 출발지로 모두 큐에 넣는다.2. 상하좌우로 돌린다3. visit 체크를 하면서 '*'은 피해준다 여기서 관건은 열쇠가 없어 지나갔던 문의 열쇠를 다시 획득하게 될 경우이다나의 케이스 같은 경우는 열쇠를 얻을 때 이전에 열쇠가 없어 지나 갔던 문들 중에 맞는 열쇠의 문을 다시 큐에 넣어 주었다.doorlist[H][W]를 만들어서 열쇠가 없지만 지나간 문들을 -1로 표시해 두었다이후, 새로운 열쇠를 얻게 될때마다 이전에 지나갔던 문과 비교해서 맞으면 다시 큐에 넣는 방식으로 하였다. 이번 문제에서 틀렸던 부분은 상하좌우로 움직일때 큐에 넣으면서 visit을 체..

문제13459 구슬 탈출 https://www.acmicpc.net/problem/1345913460 구슬 탈출2 https://www.acmicpc.net/problem/13460 풀이최소 움직인 횟수를 구하는 문제이므로 bfs 사용R구슬이 움직일때 B구슬의 위치도 중요하므로 visit[MAX R구슬][MAX R구슬][MAX B구슬][MAX B구슬] 이용bfs로 상하좌우를 탐색하며 갈 수 있는 곳을 큐에 넣어준다 여기서 중요한 점은 R구슬과 B구슬이 같은 위치에 놓일때 예외 처리가 중요한데if문을 사용하여 아래 코드와 같이 처리해주면 된다 13460 구슬 탈출2 문제는 움직이는 횟수를 구하는 문제 이므로주어진 코드를 ans를 출력하는 방법으로 바꾸어 주면 된다. 코드13459 구슬 탈출, 13460 구..

문제https://www.acmicpc.net/problem/13458 풀이간단한 for문으로 풀었다아마 더 시간을 줄일 수 있는 방법이 있을것이다 코드123456789101112131415161718192021222324#include #include using namespace std; long long int N;long long int arr[1000001];long long int B, C; int main() { cin >> N; for (int i = 0; i > arr[i]; cin >> B >> C; long long int cnt = N; for (int i = 0; i 0) { cnt += (arr[i] - B) / C; if ((arr[i] - B) % C != 0) cnt += 1..

문제https://www.acmicpc.net/problem/1726 풀이가중치 없이 최단 거리를 구하는 문제이므로 bfs 사용일단 현재 위치에서 방향에 따라 visit 처리를 해주어야 하므로 visit[MAX][MAX][5]로 해주어야 한다 이 문제를 두가지 이유때문에 틀렸는데첫번째는 최단 거리를 구하는 문제라 생각하고 습관적으로 상하좌우 방향을 모두 살폈다는 점이다이 문제는 이동거리에 따른 카운트가 아니라 명령 횟수에 따른 카운트 이다이 명령에는 turn도 명령 카운트에 들어가므로 상하좌우 방향으로 함부로 카운트 하면 안된다현재 방향에서 1,2,3 go 명령에 카운트 해주고 좌,우로 90도 turn 해준것을 카운트 한다 두번째는 주어진 방향이 내가 코드로 짜기 편하게 바꾸어야 하는데 설정을 잘못해서 ..

문제https://www.acmicpc.net/problem/2638 풀이가중치 없는 최소 거리를 구하는 것이므로 bfs로 사용외부에 닿아있는 치즈를 구할때는 dfs 사용 내부에 있는 공기는 신경 쓰지 않기 때문에 이 부분은 (0,0)에서 dfs를 시작하면 만나는 1만 queue에 넣어준다 (visit으로 체크)그러면 외부에 공기만 닿아있는 치즈만 담을 수 있다. 큐에 들어가있는 좌표의 치즈가 외부 공기에 2면 이상 맞닿아있는지 확인해야 되는데visit이 1이면서 0인 값이 상하좌우로 있나 확인하면 된다 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960..

문제https://www.acmicpc.net/problem/1600 풀이가중치 없는 최소값을 구하는 문제이므로 bfs 사용현재 위치의 x,y값과 말처럼 건넌 횟수를 담는 큐까지 총 3개의 큐 사용한번 큐를 담을때 상하좌우 4번과 말이 갈 수 있는 위치 8개를 한번에 담는다 자꾸 틀려서 고생했는데 visitd[MAX][MAX][2]로 해주어서 말로 지나가지 않았을때와 말로 지났을때 이렇게 체크를 해주었다하지만 다음과 같은 케이스에서 정확한 답을 낼 수 없다 20 1 1 1 10 0 0 0 01 0 0 1 01 1 1 1 0 20 0 1 1 10 0 0 0 01 0 0 1 01 1 1 1 0 20 1 1 1 10 0 0 0 01 0 0 1 01 1 1 1 0 문제가 첫번째처럼 주어졌을 때 왼쪽 상단 검은색..