몽셀통통의 블로그

문제https://www.acmicpc.net/problem/1938 풀이통나무가 원하는 자리에 위치할때까지 움직이는 최소 횟수에 대한 문제이므로 bfs 사용일단 x위치와 y위치, 현재 통나무 방향을 담는 큐를 세개 만들었다.중요하게 볼것은 통나무는 세칸을 차지하지만 중앙에 있는게 가장 중요하므로 중앙값만 담았다. 1. 현재 x와 y, 통나무 방향을 큐에 담는다2. 4방향으로 range 체크만 해주면서 '1'있는 칸을 제외하고 담는다3. turn하는 것도 하나로 카운트 해주므로 잊지 않고 큐에 넣어준다 첫번째 풀었을때는 문제를 제대로 안보고 풀어서 틀렸다. 케이스b와 케이스d를 보면 turn할 경우 3X3크기에서 1이 존재하지 않아야 한다.이걸 빼먹으면 바로 틀려버린다 두번째 풀었을때는 시간 초과때문에 ..

문제https://www.acmicpc.net/problem/145023 풀이dfs로 풀었는데 bfs도 가능할것 같다dfs로 3개의 벽을 차례로 놓은 후 바이러스 퍼지는 것을 dfs로 다시 구현하여 남은 0이 몇개인지 구하면 된다 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include using namespace std; int N, M,ans;int arr[9][9];int visit[9][9];int visit2[9][9];int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1..

문제https://www.acmicpc.net/problem/10026 풀이dfs를 이용한 간단한 문제이다나는 조건을 너무 더럽게 짠거 같다 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include using namespace std; int N,cnt1,cnt2;char arr[101][101];int visit[2][101][101];int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; void dfs(int x, int y,char c) { if (x = N || y = N) return; if (visit[0][x][y]|| ar..

문제https://www.acmicpc.net/problem/2665 풀이bfs를 이용하여 black이라는 배열에 현재 인덱스에서 검은방은 몇개나 바꿨는지 저장1. bfs를 이용하여 상하좌우 탐색2. 다음 인덱스 탐색하여 검은 방이 여태 몇개 있었는지 저장 2-1. 다음 방이 흰방일 경우 - 현재 인덱스와 저장된 인덱스의 값중 작은 값 저장 2-2. 다음 방이 검은방일 경우 - 현재 인덱스+1와 저장된 인덱스의 값중 작은 값 저장3. 마지막 배열에 저장된 값 출력 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include using namespa..

문제https://www.acmicpc.net/problem/3055 풀이가중치가 없고 최단 거리를 구하는 문제이므로 bfs 사용일단 물이 들어가는 큐와 고슴도치의 위치를 담는 큐 이렇게 2개를 구성한 다음큐에 물을 일단 담고 고슴도치 위치를 넣는다 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include using namespace std; int R, C,ans,flag;char arr[51][51];int smap[51][51];int wmap[51][51];int dir[4][2] = {..

문제https://www.acmicpc.net/problem/1194 코드가중치가 없고 최단 거리를 찾는 문제이므로 bfs를 사용열쇠를 찾아서 출구로 나가야한다는 점이 특이한데 비트마스크를 이용하면 된다큐를 쌓을때 4방향으로 뻗어가는 for 문에서 nkey을 변수로 안두고 했다가 고생했다 ㅠㅜ열쇠를 찾아야 하므로 한번 지났던 곳을 다시 지날 수 있으므로 3차 배열로 visit을 두었다 풀이123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include using namespace std; int N, M,flag,ans;char arr[51][51];..

문제https://www.acmicpc.net/problem/5427 풀이가중치없이 최단 거리를 구하는 것이므로 bfs를 사용불을 넣을 큐 하나와 상근이의 위치를 넣을 큐 하나씩 해서 큐를 모두 두개 사용한다.불을 넣은 큐를 일단 pop을 해주고 그 다음 상근이 큐를 pop 해준다 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include #include using namespace std; int W, H,flag,ans;char arr[1001][1001];int dir[4][2] = { {..

문제https://www.acmicpc.net/problem/2667 풀이dfs를 이용하여 단지를 라벨링 한 후,갯수를 세어 sort하여 출력 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include using namespace std; int N,num;int arr[26][26];int visit[26][26];int sortnum[700];int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; void func(int x, int y) { if (x = N || y = N) return; if (visit[x][y] || !..

문제https://www.acmicpc.net/problem/1260 풀이DFS는 DFS대로 BFS는 BFS 대로 풀면된다정점 번호가 작은 것을 먼저 방문하기 때문에 행과 열 값을 바꾸어서도 체크 해주어야 한다ㅠㅜ 이거때문에 몇번 틀렸다. 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include using namespace std; int N, M, S;int arr[1002][1002];int visit[1002]; void dfs(int num) { cout S; int n,m; queue q; for (int i = 0; i > n>>m; arr[m][..

문제https://www.acmicpc.net/problem/2146 풀이DFS+BFS를 모두 사용하는 문제1. DFS를 이용하여 모든 섬을 라벨링한다2. 모든 섬을 queue에 담는다.3. BFS와 거리 공식(|x1-x2|+|y1-y2|)를 이용하여 섬사이의 모든 거리 경우의 수 중 가장 작은 값을 구한다.(섬 중앙에서 연결이 될 경우가 있는데 어차리 최소 거리가 아니므로 상관없음) 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include #include using name..