반응형 Queue11 BOJ 2667 : 단지번호붙이기 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2667 2차원 배열의 구역을 BFS, queue를 이용해 나눠보자.집인 곳을 발견하면, 집 주변의 영역을 찾아야 한다. BFS를 이용해 푸는 방법은 다음과 같다. 1) 집이 아니면(0) 넘어간다. 2) (r, c)가 집이면 queue에 담고 visit[r][c] = 1 로 체크한다. (다음에 다시 담지 않게 하기 위해)3) (r, c)의 4방향이 집이고 visit이 0이면 queue에 담는다. 이때, queue에 담으면서 집의 개수(영역의 크기)를 센다.4) 최종 영역의 개수를 return 한다.5) 2) ~ 3)을 queue가 빌 때까지 한다. ※ BFS 탐색 과정.. 2021. 2. 27. BOJ 10845, 18258 : 큐, 큐2 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10845www.acmicpc.net/problem/18258 큐, 큐2 문제는 같지만 명령의 수가 다르다.큐는 N이 작아서 적당히 풀어도 통과할 수 있다.큐2 기준으로 풀려면 모든 명령어를 O(1)이 되도록 풀어야 한다. 큐도 메모리만 넉넉하게 잡으면 스택처럼 배열로만 풀 수 있다.스택과 다른 점은 pointer가 2개 필요하다. 큐에서 push할 때 write pointer를 증가시키고, pop할 때는 read pointer를 증가시키면 큐가 된다.그리고 read와 write의 차이가 queue의 사이즈가 된다. 현재 queue의 뒤에 값을 저장해야 하므로 wp에 값.. 2021. 2. 7. 이전 1 2 다음 반응형
