[백준 / C++] 16234번: 인구 이동 (BFS 풀이)

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 구현, 그래프 탐색, 너비 우선 탐색(BFS), 시물레이션 아이디어 DFS 또는 BFS로 풀 수 있는 문제다. 나는 아래의 과정을 통해 구현했다. 한 곳을 기준으로 BFS를 돌린다. 방문한 곳에서는 아래의 과정을 수행한다. - visited = 1로 만든다. - 인구의 수를 sum에 더한다. - 연합된 나라의 수를 센다. - 연합된 ..

• format_list_bulleted PS/백준
• · 2023. 12. 18.
• textsms

[백준 / C++] 16236번: 아기 상어 (삼성 SW 역량 테스트 기출)

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 난이도: solved.ac 골드 3 알고리즘 분류 구현, 시뮬레이션, 너비 우선 탐색 (BFS) 접근 방법 먹을 수 있는 물고기가 더 이상 없을 때까지 가장 가까이에 있는 물고기를 찾는 과정을 반복해 주면 된다. 물고기를 찾는 방식은 BFS를 이용하면 되는데, 일반적인 BFS 방식으로 구현하면 오답이 된다. 먹을 수 있는 최단 거리 내의 물고기가 여러마리일 때 왼쪽 위에 있는 물고기를 골라..

• format_list_bulleted PS/백준
• · 2023. 9. 16.
• textsms

[백준 / C++] 2206번: 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 난이도: solved.ac 골드 3 알고리즘 분류 그래프 탐색, 너비 우선 탐색(BFS) 접근 방법 지금까지 풀었던 BFS 문제에서 사용했던 visited 배열에 한 차원을 더 추가시켜 벽을 부순 적이 없는 상태에서의 방문 표시는 visited[][][0]에 나타내고, 벽을 부순 적이 있는 상태에서의 방문 표시는 visited[][][1]에 나타내었다. 큐에는 현재 위치 ..

• format_list_bulleted PS/백준
• · 2023. 8. 17.
• textsms

[백준 / C++] 9019번: DSLR

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 BFS 함수에서 현재 숫자에서 D, S, L, R 연산을 해 큐에 집어 넣는다. 그리고 visited 배열을 통해 방문한 숫자 (0 ~ 9999)를 체크하여 중복된 숫자를 방문하지 않도록 해준다. 구현 방법 현재 레지스터의 숫자를 저장할 int 형과 현재까지의 연산과정을 적은 string 형을 pair..

• format_list_bulleted PS/백준
• · 2023. 8. 7.
• textsms

[백준 / C++] 4179번: 불!

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 J가 F와 동시에 같은 지점으로 이동하면 불에 타 죽는다. 따라서 먼저 F를 이동시킨 후 J를 이동시키는 방법으로 진행했다. 다른 분들은 BFS를 두 번 돌리던데, 하나의 BFS 큐에 J와 F를 넣어서 BFS를 한 번만 돌려도 이 문제를 풀 수 있다. (이렇게 하면 메모리나 시간을 훨씬 단축시킬 수..

• format_list_bulleted PS/백준
• · 2023. 8. 3.
• textsms

[백준 / C++] 2638번: 치즈 (BFS, 구현)

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 난이도: solved.ac 골드 3 알고리즘 분류 구현, 그래프 탐색 (BFS) 접근 방법 및 구현 DFS로도 풀리겠지만 나는 BFS로 풀었다. 이 문제에서 핵심은 외부 공기와 내부 공기다. 내부 공기(구멍)는 공기로 취급 안 해서 닿아있는 공기의 개수에 포함하지 않는다. 외부 공기와 내부 공기를 파악하기 위해 우선 0인 곳을 찾아주었다. 하나의 visited 배열을 공기를 탐색하는데..

• format_list_bulleted PS/백준
• · 2023. 7. 27.
• textsms