개인사

리뷰나이트가 출발지로 부터 도착지까지 이동하는 최단거리는 구하는 문제 문제 풀이나이트가 이동할 수 있는 방향 배열을 만들어 주고, 현재의 위치와 이동 시간을 체크할 구조체를 만들어 준다.각 테케마다 출발지와 도착지를 입력 받고 bfs를 시작한다. 큐에 시작 위치를 추가하고 방문 체크용 2차배열을 만든다.while루프를 시작하고 현재 위치가 도착지라면 이동 시간을 리턴, 출력해 주면 된다. 참고 사항int dirx[] = { -1, -2, -2, -1, 1, 2, 2, 1};int diry[] = { -2, -1, 1, 2, 2, 1, -1, -2};방향 배열은 위와 같다. 정답 코드#include #include #include using namespace std;int tc, n, sx, sy, dx,..

리뷰진짜 아무리봐도 잘못된게 없는데 계속 틀려서 다시 보니 브루트포스를 돌리는 과정에서 n * m크기가 아닌 n * n크기로 돌리고 있었다... 근데 왜 97% 까지 맞는거야? 문제 풀이n 크기의 문자열을 받아와 준 뒤 n * m크기의 for문을 개행하고 현재 위치가 L일 경우 bfs를 시작한다.현재 위치와 이동 횟수 0을 큐에 넣어주고 방문 체크용 2차 배열을 0으로 초기화 하고 현 위치를 방문 체크해 준다.while루프를 돌려 4방향을 체크하고 갈 수 있는 공간이라면 방문 체크 및 이동 횟수를 1 올려 준 후 큐에 추가한다.이동 횟수가 변경 되었으므로 현재 이동 횟수가 최대 이동 횟수 보다 클 경우 갱신해 준다.for문이 종료된 후 최대 이동 횟수를 출력해 준다. 참고 사항반복문을 사용할땐 항상 범위..

리뷰인접 리스트와 방문 배열 2개를 활용하여 해결한 문제 문제 풀이노드 배열을 n + 1 크기로, 하이퍼 튜브 배열을 m + 1배열로 초기화 해준다.m * k 크기의 for문을 개행하고, 입력값을 받을 때 하이퍼 튜브와 노드의 인접 리스트에 쌍방향으로 push 해준다.큐에는 도시(노드) 정보와 이동 횟수, 현재가 노드인지 하이퍼 튜브인지를 구별할 변수를 구조체로 넣어준다.BFS를 실행하고 현재가 하이퍼 튜브일 경우 방문 처리 및 튜브 안의 노드 인자를 큐에 추가해 준다. 이때 이동 횟수를 증가 시키고 노드 정보라는 표시를 해 준다.현재가 노드일 경우 방문 처리 및 연결된 하이퍼 튜브를 큐에 추가해 준다. 이번엔 이동 횟수를 증가 시키지 않는다. 마찬가지로 하이퍼 튜브라는 표시를 해 준다.큐에서 pop한 ..

리뷰BFS로 문제를 풀었다. 굉장히 까다로웠던 문제 문제 풀이구조체 배열 busInfo를 k + 1개로 초기화 해준 후 각 버스 번호의 index에 버스 구조체를 넣어준다.이때 항상 x2가 x1보다 크고 y2가 y1보다 크다는 보장이 없기 때문에 큰 값을 x2, y2로 변환하여 넣어준다.버스 노선은 직선형 이기 때문에 x가 서로 같거나 y가 서로 같을 경우도 체크해 준 후 type 변수로 넣어준다.2차 배열 buslist를 k + 2 크기로 초기화 해준다, 각 버스 노선이 인접한 경우 쌍방향으로 index를 추가해 인접 리스트를 만들어 준다.시작점과 도착점 정보를 받아준 후 각각을 인접 리스트의 0번 index, k + 1번 index로 인접 리스트를 확장해 준다.0번 index부터 bfs를 시작해 준다..

개요그래프 : 노드와 간선으로 이루어진 자료구조완전 탐색 : 특정 노드에서 갈 수 있는 모든 노드를 확인하는 방법DFS : 깊이 우선 탐색BFS(Breadth First Search) : 넓이 우선 탐색 -> 가까운/인접한 노드부터 탐색 즉, 발견되는 노드부터 탐색한다. 위 그래프를 DFS로 탐색 한다면 0 -> 1 - > 3 -> 4 -> 2 순으로 탐색하게 된다. (깊이 우선)BFS로 탐색한다면 결과는 0 -> 1 -> 2 -> 3 -> 4 가 될 것이다. (넓이 우선, 가까운것 부터 탐색) BFS 진행 방식대기열 준비(Queue 자료 구조를 선택)시작 노드에 큐 삽입큐(대기열)에 맨 앞 노드부터 추출 및 확인(now) | 실제 탑승now를 기준으로 연결되어 있는 노드들을 큐에 등록(next 후보 검..

리뷰쉬워보이나 판별조건을 잘 설정해 주어야 하는 문제 문제 풀이방문배열을 일반 방문배열, 사다리 방문배열, 뱀 방문배열 총 세개 만들어 준다. 사다리와 뱀의 위치를 index로 이동할 위치를 value로 입력 받아준다.1부터 bfs를 시작해 주고 현재 위치부터 1 ~ 6까지 for문을 돌려준다.도착 위치가 사다리라면 사다리를 타고 해당 위치로 이동 후 방문 배열에 추가해 준다.도착 위치가 뱀이라면 뱀을 타고 해당 위치로 이동 후 방문배열에 추가해 준다.둘 다 해당하지 않다면 주사위 위치로 이동 후 방문 배열에 추가해 준다.현재 위치가 100이라면 소요 시간을 출력해 준 후 리턴해 준다. 참고 사항사다리나 뱀이 이미 방문한 위치라면 continue를 해줘야 한다. 해당 부분땜에 시간이 좀 걸렸다.  정답 ..

리뷰접근하기 정말 힘든 문제였는데 SSAFY 강의를 듣고 재정리를 하여 통과하였다. 싸피 짱! 문제 풀이각 테스트 케이스 마다 약품 사용 횟수의 최소값, 현재 약품 사용 횟수, 약품 사용 여부 리스트를 초기화 해준다.보호필름 정보를 입력 받아 주고 재귀를 실행해 준다. 이때 전달해주는 매개변수는 row가 기준이 된다.약품을 사용하지 않은 케이스, A약품을 사용한 케이스, B약품을 사용한 케이스로 나누어 재귀를 실행한다.만약 약품을 사용하지 않았다면 path에 -1을 넣어주고, cnt를 증가하지 않는다.만약 약품을 사용했다면 path에 A약품은 0을, B약품은 1을 넣어주고 cnt를 1 증가시킨다.다음 row로 재귀를 실행해 주고 위에 적용했던 처리 조건들을 복구 해준다.만약 모든 행을 다 돌았다면 모든 ..

리뷰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를 출력해 준다. 참고 사항참고해야할 조..