본문 바로가기
반응형

dfs48

BOJ 17070 : 파이프 옮기기 1 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17070 파이프는 오른쪽, 아래, 대각선으로만 진행하므로 방향을 3개 define한다. input에서는 MAP 주변에 벽을 세운다. #define MAX (16 + 5) #define RIGHT (0) #define DOWN (1) #define RIGHT_DOWN (2) int N; int MAP[MAX][MAX]; void input() { scanf("%d", &N); for (int r = 0; r 2021. 4. 8.
BOJ 16637 : 괄호 추가하기 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/16637 첫 번째 예시를 보자. 연산자는 + * - * 로 총 4개이다. 순서대로 1, 2, 3, 4번째 연산자로 정의하자. 먼저 괄호 안에는 연산자가 하나만 들어있어야 하므로, 1번 연산자에 괄호를 만들면, 2번 연산자는 괄호가 불가능하다. → (3 + 8) * 7 - 9 * 2 따라서 DFS로 아래의 경우의 수가 되도록 만든다. 0 0 0 0 → 괄호가 없는 경우 0 0 0 1 → 4번 연산자에만 괄호를 만든 경우 0 0 1 0 0 1 0 0 0 1 0 1 → 2번, 4번 연산자에 괄호를 만든 경우 1 0 0 0 1 0 0 1 1 0 1 0 1 2 3 .. 2021. 4. 5.
BOJ 19236 : 청소년 상어 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/19236 아래와 같이 FISH 구조체를 선언하여 좌표와 방향, 그리고 죽었는지 살았는지 체크하는 dead를 정의하자. 상어의 이동을 쉽게 종료하기 위해 MAP 주변은 -1로 벽을 만들고, (1, 1)부터 입력을 받자. MAP에는 물고기의 번호만 저장하고, 그 물고기 번호로 fish 배열에서 물고기의 정보를 찾는다. int MAP[6][6]; typedef struct st2 { int r; int c; int dir; int dead; }FISH; FISH Fish[17]; void input() { for (int r = 0; r 2021. 4. 3.
BOJ 17825 : 주사위 윷놀이 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/17825 시뮬레이션 문제는 시키는 대로 구현하면 된다. 이 문제에서는 파란색 화살표가 핵심이다. 파란색 화살표에 시작할 경우는 방향이 바뀌기 때문이다. 이런 경우는 그냥 처음부터 움직여야하는 방향에 대한 답을 적어두고 시작하면 된다. 먼저 왼쪽의 점수판은 오른쪽 그림처럼 번호를 매겨 1차원 배열로 만든다. 그러면 아래와 같이 input에서 미리 답을 적어둘 수 있다. int dice[10 + 5]; int next[32 + 5][6]; int score[32 + 5]; int board[32 + 5]; int horse[5]; void input() { for .. 2021. 3. 28.
BOJ 18139 : Rush Hour Puzzle (해시, 2차원 배열 탐색) 삼성 B형 전체 링크 www.acmicpc.net/problem/18139 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 내용을 번역해서 요약하면 아래와 같다. 1) 6 x 6 board에서 자동차가 최대 10개 존재한다. 2) 자동차는 1칸씩 움직이며, 길이가 2 또는 3이다. 3) 1번 자동차가 exit로 탈출해야 한다. 4) exit는 항상 3번째 줄의 오른쪽 끝이다. 따라서 1번 자동차는 항상 3번째 줄에 가로로 존재한다. 5) 최대 10칸까지 움직인다. 그 이상 움직여도 1번 자동차가 exit로 탈출 못하면 -1을 출력한다.. 2021. 3. 18.
BOJ 17142 : 연구소 3 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/17142 연구소 문제와 다른 점은 벽을 세우는 것이 아니고, 바이러스를 M개 선택해야하는 것이다. 바이러스의 선택 → DFS 경우의 수 : 조합 문제 바이러스의 확산 → 토마토 문제를 같이 조합해서 풀면 된다. 먼저 문제를 풀기 편하게 input을 받으면서 MAP을 재변경하자. 벽(1)과 바이러스(2)를 그대로 두면, 바이러스가 몇초 뒤에 퍼지는지 셀 때, 구분하기 까다롭다. 따라서 벽은 -1로, 바이러스는 -2로 표시하자. 또한, 바이러스는 따로 배열에 저장해두자. typedef struct st { int r; int c; }RC; RC virus[MAX*M.. 2021. 3. 17.
BOJ 15686 : 치킨 배달 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/15686 input을 받을 때, 치킨집과 집의 좌표를 받아두자. void input() { scanf("%d %d", &N, &M); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { scanf("%d", &MAP[r][c]); if (MAP[r][c] == 1) { house[hcnt].r = r; house[hcnt++].c = c; } else if (MAP[r][c] == 2) { chicken[ccnt].r = r; chicken[ccnt++].c = c; } } } } 이제 선택할 치킨집 리스트.. 2021. 2. 25.
BOJ 15685 : 드래곤 커브 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/15685 방향을 먼저 모두 만들고, 시키는 대로 그리면 된다. 먼저 움직이기 위한 배열 dy, dx를 선언하자. 0: x좌표가 증가하는 방향 (→) 1: y좌표가 감소하는 방향 (↑) 2: x좌표가 감소하는 방향 (←) 3: y좌표가 증가하는 방향 (↓) int dy[] = { 0, -1, 0, 1 }; int dx[] = { 1, 0, -1, 0 }; 이제 moveList를 만들자. 드래곤 커브의 규칙대로 처음 방향이 3인 경우, moveList는 아래와 같이 만들어진다. (직접 그려보자) L = 0 : 3 L = 1 : 3 0 L = 2 : 3 0 1 0 L.. 2021. 2. 25.
BOJ 15684 : 사다리 조작 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/15684 먼저, 사다리를 구성하는 MAP 주변을 벽(3)으로 만들자. 그리고 사다리 설치는 1 → 2로 설치하자. void input() { scanf("%d %d %d", &N, &M, &H); for (int r = 0; r 새로운 2번째 사다리 설치 -> 3개 설치 -> 다음 3개 설치 ... -> 3개 설치 종료. ... 새로운 1개 설치 -> 2개 설치 -> ... -> 3개 설치 종료. ... 와 같은 방식으로 사다리를 설치하게 되고, 1개에 답이 있음에도 불구하고, 2개 설치와 3개 설치를 병행해야 한다. 따라서 DFS에 최대 몇 개까지 설치할지 정.. 2021. 2. 24.
반응형

티스토리툴바