hotamul의 개발 이야기

url: https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 핵심 1. 본 문제는 bfs 문제로 head 만을 이용한 linked list로 쉽게 풀 수 있다. 기본적으로 list의 들어오는 순서가 중요한 경우가 많으므로 이번엔 tail을 가지고 있는 linked list로 풀이해보고자 한다. 풀이에 대한 내용은 head만을 이용한 linked list 링크를 참조하자 2. head, tail을 가지고 있는 linked list 구조체 struct..

url: https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 핵심 1. dfs/bfs 문제 2. 문제는 매우 간단하지만 Pro 시험에서 Linked List 자료구조는 필수로 구현할 줄 알아야 하므로 Linked List를 이용해 풀이해보고자 한다. 이 문제는 바이러스 문제와 달리 초기화를 해줘야 한다. linked list 구현은 바이러스 문제와 같고 (Tail 포인터를 사용하지 않고) 초기화 함수만 추가된 것이다. 3. linked lis..

url: https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 핵심 1. bfs 문제 2. 문제는 매우 간단하지만 Pro 시험에서 Linked List 자료구조는 필수로 구현할 줄 알아야 하므로 Linked List를 이용해 풀이해보고자 한다. 3. Linked List는 추가 연결이 필요할 때 연결 끝 부분 (Tail) 에 추가해줘야 하는 경우, 즉 list의 연결 순서가 중요할 경우 tail을 알 수 있도록 해서 tail 다음에 추가로 노드 연결..

url: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 핵심 1. BFS 문제 2. 큐에 push 할 때 조건 (터널이 연결되어 있음) 을 잘 구현해야 한다. 먼저 터널 종류에 따른 방향 정보가 담긴 dr[7 + 1][4], dc[7 + 1][4] 배열을 미리 만들어 준다. 이 때 행은 터널 구조물 타입을 의미한다. 따라서 맵을 탐색하며 map[r][c] 에 0이 아닌 수가 들어 있다면 터널이 연결되어 있는지를 확인한다. 터널이 연결되어 ..

url: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3561&sca=99 JUNGOL www.jungol.co.kr 풀이 핵심 1. 가장 가까우면서 나보다 크기가 작은 먹이를 찾는 방법을 구현하는 것이 중요하다. (BFS로 구현) 거리가 같을 경우 행 index가 작은 순서로, 행 index가 같을 경우 열 index가 작은 순서로 탐색해야 한다. 그리고 나보다 크기가 작은 먹이를 찾았다면 위치 및 거리를 return 해줘야 한다. 여기서 나보다 작은 먹이를 찾지 못했다면 프로그램을 종료한다. 거리가 같을 경우 / 행 index가 같을 경우를 고려해야 하므로 우선순위 큐를 사용했다. STL 큐는 sort에 사용할 수 없고 priority_queue를..

SWEA 1249. [S/W 문제해결 응용] 보급로 문제 풀이 핵심 1. BFS 문제 2. 경로의 시간을 저장하는 check 배열을 모두 9 * 100 * 100 으로 초기화 한다. (9 * 100 * 100이 가장 큰 값) 3. 새로운 곳(nr, nc)에 방문 할 때 check[nr][nc] 보다 check[cur.r][cur.c] + map[nr][nc] 가 작을 경우에만 큐에 push 한다. 여기서 cur은 현재 위치 정보가 담긴 struct 이다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int T, N; int map[100][100]; int check[100][100]; struct POS { int ..

url: https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 핵심 1. 최소 구슬을 굴리는 (기울이는) 횟수 구한는 문제 --> BFS로 풀이 2. 빨간 구슬, 파란 구슬의 시작 위치를 red_sr, red_sc, blue_sr, blue_sc 에 저장한다. 3. 4차원 배열인 check 배열을 활용해 중복 방문을 방지 한다. ... bool check[10][10][10][10]; ... /..

url: https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 핵심 1. Bruth Force + BFS 문제 2. blank 변수에 빈칸 (0)의 개수를 저장 한다. 3. virus를 활성화 시킬 수 있는 장소(2)의 위치 (r, c) 를 virus 배열에 저장한다. (virus_size 변수에 virus 배열 장소 개수도 같이 저장) 4. 활성화 위치를 저장할 vector picked를 생성하고 재귀 형식의 dfs 함수에 전달한다. dfs 함수는 v..

url: https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 핵심 1. 최단 거리 --> bfs 문제 (+ 시뮬레이션) 2. 벽을 모두 -1로 변경 3. 현재 위치 cur_r, cur_c에 저장 4. 손님이 있는 곳을 고유한 ID (1, 2, 3, …)로 map에 표시 한다. 손님의 위치와 도착 위치를 target 배열에 표시 한다. 이 때 target 배열의 index는 손님의 ID로 한다. 5. fi..

url: https://www.acmicpc.net/problem/1600. 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 핵심 1. BFS 활용 2. 벽 부수기 문제와 비슷한 풀이 3. 방문 여부는 check[r 좌표][c 좌표][말 점프 횟수] 4. 말 점프 횟수가 K 이면서 dir (방향 index) 가 4 이상이면 break 5. (R - 1, C - 1) 좌표에 도달하면 거리 return, 모든 탐색을 완료해도 도착지에 다다르지 못할 경우 -1 return 코드 #define ..