본문 바로가기
반응형

Algorithm45

백준 7576 토마토 - C++ 접근 입력이 주어졌을 때 익은 토마토를 전부 q에 넣고 bfs 탐색을 시작한다. 만약 아직 익지 않은 토마토가 있다면 출력은 -1 그렇지 않다면 모든 토마토가 익는데 걸린 시간 출력 #include #include using namespace std; int A[1001][1001]; int check[1001][1001]; int low[] = {-1, +1, 0, 0}; int col[] = {0, 0, -1, +1}; int M, N; int bfs(){ queue q; // 익은 토마토 찾아서 q에 넣기 for(int i=1; i M >> N; for(int i=1; i A[i][j]; } } int cnt = bfs(); for(int i=1; i 2020. 7. 27.
백준 2178 미로 탐색 - C++ BFS를 이용한 최단거리 구하기 문제이다. (1,1)에서 시작하여 (N,M)으로 가는 최단거리를 구해야 한다. 현재 위치(i,j)에서 다음 위치(상하좌우)로 갈 수 있을 때 다음 위치의 값을 현재 위치의 값 +1로 하게 되면 최종적으로 (N,M)으로 가는 최소 비용을 구하게 된다. #include #include using namespace std; int A[101][101]; bool check[101][101]; int low[] = {-1, +1, 0, 0}; int col[] = {0, 0, -1, +1}; int N,M; void bfs(int i, int j){ check[i][j] = true; queue q; q.push(make_pair(i,j)); while(!q.empty()){ i.. 2020. 7. 26.
백준 2667 단지번호붙이기 - C++ 접근 그래프 문제라고 생각하면 문제에 쉽게 접근할 수 있다. 핵심 개념은 연결 요소가 무엇인지 DFS 또는 BFS가 무엇인지 알고 있으면 좋다. 각 단지는 서로 연결되어 있지 않기 때문에 각각을 연결 요소라고 생각해도 좋다. 각 집은 어떠한 집 기준으로 상하좌우 중 한 곳에 위치해 있으면 연결되어 있다고 본다. 행렬에서 어떠한 집(A[i][j])에서 상하좌우는 (i,j-1),(i,j+1), (i-1, j), (i+1,j)의 값과 동일하다. DFS #include #include #include #include using namespace std; int A[26][26]; bool check[26][26]; vector vectorCnt; int cnt = 0; void dfs(int i, int j){.. 2020. 7. 26.
백준 1248 맞춰봐 - C++ 음 문제가 엄청 길다. 필요한 내용이 중간 중간 있을까봐 전부 꼼꼼히 읽었지만 마지막 부분만 읽으면 된다.. 규현이는 -10~10까지 알고 있기 때문에 총 21가지 수를 쓸 수 있다(0포함) 만약에 규현이가 A= [-2, 5, -3, 1]이라는 수를 말한다면 이것을 2차원 배열 S에 다음과 같이 표현할 수 있다. 0 1 2 3 0 - + 0 + 1 X + + + 2 X X - - 3 X X X + S[i][j]는 A[i]부터 A[j]까지의 합이 양수면 +, 음수면 -, 0이면 0을 나타낸다. 여기서 i는 j보다 작거나 같아야 한다. i가0이고 j가 1이라 해보자 A[0]+A[1]이 되고 이것의 합은 3이기 때문에 S[0][1]에 +가 저장된다. i가 0이고 j가 2이라면 A[0]+A[1]+A[2]가 되고.. 2020. 7. 23.

티스토리툴바