너비우선탐색3 [백준 1944번] 복제 로봇 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 처음 문제를 읽어보고 나면 어떤 방법으로 접근해야 할지, 조금 막막하게 느껴질 수 있는 문제입니다 (제가 그랬음). 시작점에서 특정 도착점까지의 최단 거리를 구하는 방법에는 여러 가지가 있지만, 이렇게 격자 형식으로 판이 주어지는 경우에는 bfs가 편리합니다. 또, 이런 경우도 있을 수 있습니다. 시작점 S에서 도착점 A, B, C가 .. 2021. 9. 1. [백준 16236번] 아기 상어 이 문제는 삼성 SW 역량 테스트 기출문제 입니다. 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS를 이용한 탐색을 핵심으로 하는 문제입니다. BFS에 대한 이론적 배경은 여기를 참고하세요. BFS를 실제로 이용하여 문제를 푸는 접근법이 아직 생소하여, 인터넷 검색을 많이 활용했습니다. 문제가 내용이 긴데, 요약하면 아래와 같습니다. 상어는 본인보다 작은 물고기만 잡아먹을 수 있다. 상어는 빈 공간 혹은 자기보다 .. 2020. 11. 23. [백준 17501번] 수식 트리 난이도: 골드 1 문제 링크: www.acmicpc.net/problem/17501 17501번: 수식 트리 수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다. 연산자 노드는 항상 두 개 www.acmicpc.net 제겐 아직 너무나도 생소한 bfs를 이용하는 문제입니다. DFS는 그래도 문제 한 두 개 풀어봐서 기억이라도 하는데, BFS는 자료구조 책에서만 접해봐서 너무 생소했어요. 접근 방법을 열거하자면... 시작에 앞서, tree_node 구조체를 만든다. 이 구조체는 연산자, 왼쪽 자식 노드, 오른쪽 자식 노드, count 변수를 멤버로 가진다. 전역 array num, sub,.. 2020. 11. 8. 이전 1 다음
