본문 바로가기

백준24

[ 백준 3197 ] 백조의 호수 (C++) [문제보기] [해결과정] 1. 입력 받기 (n, m , arr[][]) -> 백조 구조체를 생성하여, 0번 백조 1번 백조 입력 받기. -> 물일 경우 ( . ) wq(큐)에 넣기 2. q(큐)에 0번 백조 좌표 넣기 3. 결과를 도출할 날짜 ans =0으로 셋팅 후 무한 반복문 실행 4. nq( q와 동일한 큐 )생성 5. 0번 백조 돌리기 (q를 다 돌때까지) -> 만약 X라면 nq에 좌표 넣기 -> 만약 X가 아니라면 q에 좌표 넣기 ★★★0번 백조가 돌아다닐 수 있는 범위를 탐색하는 것임! 6. q에 nq를 넣기 7. 얼음 부수기 -> int s 에 wq.size() 값 대입 -> while(s--) 반복문 BFS 실행 -> 만약 X라면 wq에 좌표 넣고 해당 좌표 값을 '.'으로 변경 ★★★ 여.. 2020. 2. 26.
[ 백준 2146 ] 다리 만들기 (C++) [문제보기] [해결과정] 1. 입력 받기 (n, arr[][]) 2. 섬 번호 메기기 -> group 변수 선언 (섬 번호 Count) -> arr 배열을 돌면서, 1이면서 방문하지 않은 곳이라면 q(큐)에 좌표 넣기 -> 해당 좌표에 map배열에 gNum 입력과 방문체크 후 BFS() 실행 ★★★ 여기서 섬들의 좌표가 잘 찍혔는지 map을 print 해서 디버깅 한번 해보기!!! 3. 반복문을 사용해 섬번호 1번부터 끝번호까지 탐색 -> check배열 초기화 -> func(섬번호) 함수 실행 4. func(섬번호) 함수 -> arr 맵을 돌며 섬번호와 같은 좌표는 q2( y좌표, x좌표, cnt(초기값0) ) 삽입 -> q2에 대한 bfs 실시 -> 만약 다음 노드가 방문하지 않은 곳이고, 맵에서 0 .. 2020. 2. 26.
[ 백준 1926 ] 그림 (C++) [문제보기] [해결과정] 1. input -> n, m (세로, 가로) 변수, arr (map 2차원 배열) 2. arr 맵을 돌며, arr[i][j]==1 이고, check[i][j]==0 (방문하지않음) 이라면, 진입 -> group(집합 갯수)를 +1 시키고, cnt(원소 갯수)를 1로 초기화한다. -> ★★★그리고 만약 maxCnt(최대 원소 갯수) 보다 cnt가 크면 maxCnt == cnt; -> check[i][j]==1로 방문체크를 한다. -> queue에 i,j좌표를 삽입하고, BFS()로 진입한다. 3. BFS -> 주변 4방향을 탐색하며, arr[i][j]==1이고, check[i][j]==0 인 곳 진입 -> cnt(원소 갯수)++; -> 그리고 만약 maxCnt(최대 원소 갯수) .. 2020. 2. 24.
[ 백준 17822 ] 원판 돌리기 (C++) [문제보기] [해결과정] 1. deque 2차원 배열 생성. 2. deque에 값 넣기. 3. 문제 입력 받기 (돌릴 내용) 4. turn 함수 실행 전, x의 배수 만큼 돌릴 수 있도록 반복문 설정 후 turn 진입 - 만약 시계 방향이라면, 뒤에 것을 앞으로... - 만약 반시계 방향이라면, 앞에 것을 뒤로... 5. 같은 숫자 지우기 - 절대값으로 비교 ! 좌우, 앞뒤, *** 가장 중요한 맨앞, 맨뒤 *** ---> 같은 수라면 음수로 설정 - 절대값으로 비교하는 이유 : 이미 발견된 수가 있을 수 있으므로... - 만약 같은 숫자를 단 한번이라도 지운 적이 있다면 flag 변수 설정 - 모든 작업 후에, 음수인 숫자를 0으로 변경 6. 만약 같은 숫자가 하나도 없었더라면, - deque에 있는 .. 2020. 2. 19.
[ 백준 1238 ] 파티 (C++) [문제보기] [해결과정] 1. 2차원 배열 초기값을 -1로 셋팅 2. input : v[a][b] = c ---> a에서 b까지 가는데 c시간이 걸린다. 3. 2차원 배열을 순회하며 -1인 값을 987987987(최대 값)으로 변경 4. 플로이드 와샬 알고리즘 실행 5. 모든 노드에 대한 탐색을 실행 -> i에서 x까지의 거리, x에서 i까지의 거리를 합하고 ans와 비교하여 큰 값 갱신 [소스코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 6.. 2020. 2. 12.
[ 백준 17825 ] 주사위 윷놀이 (C++) [문제보기] [해결과정] 1. 윷놀이 판을 구현 (map 초기화/설정) -> 해당 노드에 다음 이동할 노드 번호를 저장 (map 배열) -> 방향 전환이 되는 노드를 따로 관리 (turn 배열) -> 각각의 노드의 점수를 관리 (score 배열) -> 해당 노드에 말이 있는지 없는지 확인 배열 (check 배열) 2. 주사위는 무조건 10번 던지니까, 10번 횟수 기록 (arr 배열) 3. 말은 총 4마리로 움직임 -> 순열 구현 ( 각각의 주사위로 인하여 어떤 말을 움직일지 모르니 완전 탐색 DFS 구현) 4. 말의 움직임 -> 현재 말의 위치, 말이 도착할 위치, 주사위의 갯수 총 3개의 변수 필요 -> 예외 처리 : 만약 현재 위치가 변환점이라면, turn 배열을 이용하여 위치 변환 : 만약 도착 .. 2020. 1. 28.
[ 백준 9205 ] 맥주 마시면서 걸어가기 (C++) [문제보기] [해결과정] 1. 좌표를 저장할 배열 arr[MAX][2] 와 방문 체크할 배열 check[MAX] 준비 2. 집(0번 순서) 부터 편의점(1부터 N까지 순서), 마지막 도착지 (N+1번 순서) 까지 입력 받음 3. BFS() 3-1. 좌표의 절대값 (x 비교값 + y 비교값) 이 1000 이하여야 이동가능! [소스코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #include #include .. 2019. 12. 17.
[ 백준 1079 ] 마피아 (C++) [문제보기] [해결과정] 1. 총 4가지 입력 (1. 사람 수, 2. 사람 마다 각각의 점수, 3. 2차원 배열의 점수표, 4. 은진이 IDX) 2. DFS (브루트포스) 2-1. 기저조건 : 은진이가 죽거나, 남은 사람이 1명 일 때... 2-2. 현재 인원이 짝수일 경우 (밤) 2-2-1. 사람 수 만큼 for문을 돌며, 은진이거나 이미 죽은 사람 인덱스라면 continue; 2-2-2. 그렇지 않으면 해당 인덱스 사람을 죽이고, 나머지 살아있는 사람들의 점수를 변경 2-2-3. DFS 실행 (사람-1, 날짜+1) 2-2-4. 시행 후 위 과정을 반대로 시행 2-3. 현재 인원이 홀수일 경우 (낮) 2-3-1. 점수가 가장 높은 사람 찾기 2-3-2. 은진이가 가장 점수가 높을 경우 기저조건 시행 2.. 2019. 12. 11.
[ 백준 1113 ] 수영장 만들기 (C++) [문제보기] [해결과정] 1. 입력 받을 때 0,0 부터가 아닌 1,1 부터 2019. 12. 8.

티스토리툴바