본문 바로가기

코딩 테스트 연습/백준16

[Python]Baekjoon 21736번: 헌내기는 친구가 필요해(BFS) 1. 문제 https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 캠퍼스(그래프)를 이동하면서 주인공이 만날 수 있는 사람의 수를 구하는 문제이다. O는 빈공간, P는 사람, X는 벽, I는 주인공의 위치이다. 2. 풀이 첫번째로 주의해야 하는 부분은 그래프의 입력을 공백 단위로 받지 않고 문자열로 받고 있다는 점이다. 처음에는 조금 당황했는데 그냥 똑같이 list에 넣으면 똑똑한 파이썬이 알아서 처리해주었다. 두번째로 주의해야 하는 부분.. 2024. 3. 15.
[Python]Baekjoon 7569번: 3차원 토마토(BFS) 1. 문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net N, M 개의 칸에 토마토가 들어있고 이 상자를 H층만큼 쌓아 올린다. 0은 익지 않은 토마토, 1은 익은 토마토, -1은 빈칸을 의미한다. 익은 토마토와 인접해 있는(상, 하, 좌, 우, 위, 아래) 토마토는 하루가 지나면 익는다. 토마토가 모두 익는데 며칠이 걸릴까? 2. 풀이 최소 일수를 구하는 문제는 BFS를 이용한다. 7576번 토마토 문제와 동일한 로직.. 2024. 3. 13.
[Python]Baekjoon 7576번: 토마토(BFS) 1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net N, M 개의 칸에 토마토가 들어있다. 0은 익지 않은 토마토, 1은 익은 토마토, -1은 빈칸을 의미한다. 익은 토마토와 인접해 있는(상, 하, 좌, 우) 토마토는 하루가 지나면 익는다. 토마토가 모두 익는데 며칠이 걸릴까? 2. 풀이 지금까지 익숙하게 풀어왔던 BFS에 조금 더 생각을 해야 하는 문제였다. 가장 핵심적인 부분은 BFS의 시작 지점이 여러 개인데 이를 .. 2024. 3. 11.
[Python]Baekjoon 1697번: 숨바꼭질 1. 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 시작 지점과 도착 지점을 입력받는다. 시작 지점에서 x+1, x-1, x*2 세 가지 방법을 활용해서 최대한 빨리 도착 지점으로 가는 문제이다. 최대한 빨리 갔을 때 몇 번 이동했는지 출력하면 된다. 2. 풀이 최단 시간 길 찾기 문제이므로 BFS를 활용할 것이다. BFS 함수에서 시작하는 좌표를 전달받고 큐에 넣어준다. 일반적인 길찾기 문제와 달리 이 문제는.. 2024. 3. 5.
[Python]Baekjoon 17478번: 재귀함수가 뭔가요? 1. 문제 https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 출력예시에 맞게 챗봇의 응답을 출력하는 문제이다. 문제 이름에서도 알 수 있듯이 재귀함수를 활용해야 한다. 입력과 출력의 예시는 다음과 같다. 2. 풀이 입력받은 숫자 T는 재귀함수를 몇 번 호출하는지를 나타내는 숫자이다. 최초로 함수가 한번 호출되고, 재귀로 T번 호출되기 때문에 함수는 총 T+1번 실행이 되는데 이 부분을 생각하는 게 포인트였다. 우선 주어진 예시에서 각 문장이 어.. 2024. 3. 4.
[Python]Baekjoon 2178번: 미로 탐색(BFS) 1. 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다. 2. 풀이 BFS 알고리즘을 활용하여 풀이할 것이다. BFS 하면 queue바로 떠올려야 하고 queue하면 deque가 바로 떠올라야 한다. 행렬 역시 그래프로 생각할 수 있으므로 주어진 행렬을 그래프에 저장한다. 그래프에서 (N, M)까지 가는 길은 연결되어 있으므로 BFS 함수는 한번만 호출해주면 된다. BFS.. 2024. 3. 3.

티스토리툴바