개인사

리뷰DFS와 브루트포스 알고리즘이 접목된 문제문제 풀이배열을 초기화 해줘야 한다. 각 테케의 데이터를 1 ~ N로 받고 나머지는 -1로 초기화 해준다.출발한 카페로 돌아와야 하니 각 DFS를 실행할때 현재 위치의 좌하 방향의 좌표를 도착지로 설정해 준다.경로상에 같은 카페가 있으면 안되니 방문 처리를 해줘야 한다. 방문한 좌표의 값을 v배열의 인덱스로 방문처리지나온 길에 대한 정보를 기억해야 한다. path 벡터에 기록해 준다. (길이를 구하는 문제이니 아무 값이나 들어와도 상관x)도착지에 도달했을 경우 path벡터의 길이가 방문한 카페의 길이가 된다. 최대값을 ans변수에 기록해 준다.모든 좌표에 대한 DFS가 종료된 경우 ans의 값이 4보다 작으면 -1로 변경 (완벽한 사각형이 만들에 진게 아니다...

리뷰SSAFY 백트래킹 시간에 배워서 풀었다. 싸피 짱! 문제 풀이DAT 배열을 총 세개 만들어 준다. col 기준, 우하향, 좌하향 대각선에 방문 체크를 하기 위함우하향, 좌하향 DAT의 index로 전달해 줄 값을 저장할 2차 배열 2개를 만들어 준다.우하향 배열은 우하향 대각선의 값이 같게, 좌하향 배열은 좌하향 대각선의 값이 같게 만들어준다. 값은 DAT의 범위 내에 있고, 각 대각선과 값이 겹치지 않는다면 상관 없다.row를 매개변수로 0부터 백트래킹을 시작한다. 만약 row가 n과 동일하다면 배치가 가능한 것이다. cnt를 1 더해준다.for문을 시작하고 0부터 n까지 순회를 돈다. 위에서 말했듯 행은 현재 재귀의 row로 받고 있다.현재 열에 놓을 수 있다면 (판별 조건을 통과했다면) 모든 ..

리뷰쉽게 생각했다가 푸는데 한시간은 걸린 문제 생각지 못한 까다로운 조건이 많다. 이래서 설계를 하고 풀어야 하는데.. 문제 풀이n개의 줄에 노드간 상관 관계를 받아준다. -1이 주어졌을땐 해당 인덱스를 루트 인덱스로 따로 저장해 주자인접 리스트 형태가 완료 되었다면 삭제할 값을 받아오고 해당 인덱스의 벡터를 날려주자루트 인덱스부터 dfs를 시작한다. 이때 루트가 비어있다면 리턴을 해주자 (루트가 삭제된 케이스)현재 노드의 자식을 순회하고, 만약 삭제된 노드를 만났는데 현재 노드의 크기가 1일 경우 cnt를 1개 올린다.자식의 리스트가 비어있다면 cnt를 올리고 다음 요소를 순회한다.둘 다 해당되지 않으면 해당 인덱스를 dfs 해준다. dfs가 전부 종료되면 cnt를 출력해 준다. 참고 사항참고해야할 조..

리뷰최소 힙과 최대 힙을 사용하여 문제를 풀이하였다.처음엔 스택을 사용하려 했으나 인입되는 순서 관리 골치아파서 힙으로 풀릴 것 같아 힙을 사용하였다. 문제 풀이n, k, t 값을 받아와 주고 최소힙과 최대힙을 초기화 해준다.t보다 크거나 같은 값은 bigger로, 작은 값은 lower 힙으로 보내준다.cnt가 k보다 작을 경우 while루프를 돌려 lower에서 가장 큰 값을 t에 더해주고 해당 요소를 빼준다.요소를 빼주고 나서는 변경된 t값에 맞추어 최소힙과 최대힙을 최신화 해줘야 한다. 참고 사항lower에서 가장 큰 값을 빼주기 전에 while문을 통해 bigger에 존재하는 t보다 작은 값들을 lower로 옮겨 주었다.  정답 코드#include #include #include using nam..

리뷰3차 배열의 BFS문제 문제 풀이3차 배열을 사용해야 하므로 방향을 총 6개를 설정해 줘야 한다. 상, 하, 좌, 우, 위, 아래n, m, h값을 입력받고 3차 배열에 값을 넣어준다. 이때 값이 1일경우 미리 큐에 넣어주면 편하다.bfs를 실행하고 3차 배열의 범위 내를 탐색한다. 나는 다음 좌표가 만약 값이 0인 경우 time + 2를 해주었다.bfs가 종료된 후 토마토가 잘 익었는지 확인해 주어야 한다. flag와 max_val 변수를 각각 0으로 초기화 해줬다.3차 배열을 돌며 만약 0이 발견되면 flag = 1, break 해준다. 그게 아니라면 max_val에 최대값을 저장해 준다.flag가 1일경우 -1을 출력, 0일 경우 max_val을 2로 나눈 값을 출력해 주면 된다. 참고 사항tim..

리뷰케이스를 2개로 나누어 BFS를 활용하여 푸는 문제 문제 풀이n값과 2차 배열을 입력받은 후 2차 배열을 한개 더 생성 후 초기화 해준다. (깊은 복사 필요)0, 0부터 n-1, n-1 좌표까지 순회를 하며 만약 각 배열의 현재 좌표 값이 '_'가 아니라면 각각의 bfs를 실행해 준다.bfs1은 각 색상이 주어졌을때 해당 색상이 있는 부분은 모두 '_'로 바꿔주고 case1 즉, bfs1 실행 횟수를 증가 시킨다.bfs2는 위와 동일하나 만약 색상이 R 혹은 G일경우 R, G모두 '_'로 바꿔주고 case2를 증가 시킨다.2차 배열의 모든 순회와 bfs처리가 종료된 후 case1과 case2를 출력해 주면 된다. 참고 사항없음  정답 코드#include #include #include using na..

리뷰재귀와 BFS가 결합된 형태로 문제를 풀었다. 문제 풀이n, m을 입력받고 n * m 크기의 2차 배열에 값을 받아준다. 이때 값이 2일경우 해당 좌표를 큐에 미리 추가해 둔다.2차 배열을 순회하며 만약 값이 0인 좌표를 만난다면 해당 값을 1로 변경하고 현재 좌표 및 설치한 벽의 개수 1개를 wall함수의 인자로 전달해 실행해 준다. 이후 1로 변경한 값을 다시 0으로 변경한다.wall 함수는 위에서 0으로 바꿨던 좌표 위치부터 2차 배열을 순회하고 0을 만났다면 1로 변경, 벽의 개수 증가.만약 벽의 개수가 3개라면 dfs실행, 아니라면 wall을 재귀 호출한다. 이후 다시 0으로 변경, 벽의 개수 감소.bfs 함수에서는 현재 2차 배열과 큐를 깊은 복사를 해주고 넓이 우선 탐색을 진행해 준다.w..

리뷰어차피 불에 닿으면 타죽으니 범위를 지정해 주지 않아 OutOfBounds 에러가 떴다. 다시 생각해 보니 범위는 꼭 지정해 줘야 했다.기존의 BFS문제와 같지만 지훈이와 불의 입장에서 모두 생각해 주어야 하는 문제 문제 풀이r, c와 미로 정보를 받아준다. 나는 1차 문자열 배열로 미로를 받아와 주었다.좌표 및 지훈이 여부, 시간 등의 정보를 pos 구조체로 정의해 주었다.큐대신 덱으로 받아와 만약 지훈이의 위치라면 push_front를, 불의 정보랑 push_back으로 정보를 받아와 줬다. 이때 j변수를 불이라면 0, 지훈이라면 1로 초기화 해주고, t변수를 지훈이라면 1, 불이라면 0으로 초기화 해줬다.while 루프를 시작하고 pop 후 현재 위치가 가장자리면서 지훈이라면 time을 리턴해 ..

리뷰C++, 파이썬 모두 힙을 사용한 BFS로 문제를 풀었다. 문제 풀이m과 n을 입력받고 2차 배열을 입력 받는다, 방향 배열을 4방향으로 초기화 한 후 방문 배열도 n * m크기로 초기화 한다.힙에 (벽을 부순 횟수, x좌표, y좌표)를 초기화 해준다. 초기값은 (0, 0, 0)이다. 최소 벽을 출력할 min_wall 변수도 0으로 초기화 해주고 while 루프를 실행한다.현재 힙에 존재하는 벽이 가장 낮은 정보를 뽑아온다.만약 끝부분에 도달했다면 현재 까지 부순 벽의 수를 min_wall에 저장해 준다.그게 아니라면 4방향을 체크하며 범위 내에 존재하는지, 방문을 한적이 있는지를 체크해 준다.만약 방문을 하지 않은 좌표라면 방문 처리를 해주고, 해당 좌표의 값이 1이라면 부순 벽을 1만큼 올려준 뒤..

리뷰전위, 중위, 후위 순회 겁먹지 말고 그냥 출력 시점만 조정해 주면 된다.우선 문제는 굉장히 친절하다, A, B, C 오름차순으로 주어지고 루트는 항상 A고 좌우 노드 모두 친절히 설명해 준다. 문제 풀이맵을 통해 앞의 노드를 키로 갖고 뒤의 값 두개를 pair로 받아준다.A를 시작으로 dfs를 돌려주고 '.'가 아닌 노드를 왼쪽부터 방문해 주면 된다.전위 순회 : dfs 재귀를 실행하기 전에 루트 노드부터 출력 해준다.중위 순회 : 왼쪽 노드 재귀를 실행한 후 루트 노드를 출력해 주면 된다.후위 순회 : 왼쪽 및 오른쪽 노드 모두 재귀를 실행해 주고 나서 루트 노드를 출력해 주면 된다.각 dfs 실행 사이에 줄바꿈을 한번씩 해주면 된다. 참고 사항 정답 코드#include #include #incl..