본문 바로가기

백준

[백준] 27652번 AB
[백준] 27652번 AB https://www.acmicpc.net/problem/27652 27652번: AB 집합 $A, B$와 문자열 $S$에 대하여, 다음 쿼리를 수행하는 프로그램을 작성하시오. add A $S$: $A$에 $S$를 추가한다. delete A $S$: $A$에서 $S$를 제거한다. add B $S$: $B$에 $S$를 추가한다. delete B $S$: $B$에서 $ www.acmicpc.net 이문제는 집합 A의 부분 문자열과 집합 B의 부분 문자열을 합쳐서 문자열 S를 만들 수 있는 경우의 수를 구하는 문제입니다. 🎲 문제 풀이법 1. 문제에서 주는 쿼리에 맞게 문자열을 트라이 구조체로 저장하여 줍니다. 이때, B집합의 문자열은 접미사가 되기 때문에 문자열을 역순으로 저장해 줍니다. 2. 이때 트라이 ..
[백준] 17472번 다리 만들기 2
[백준] 17472번 다리 만들기 2 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이 문제에서는 섬과 바다를 2차원 배열의 형태로 제공합니다. 그리고 해당 섬들을 모두 잇는 최단 길이를 구하는 문제입니다. 🎲 문제 풀이법 1. 우선, 각각의 섬을 구별하는 작업부터 해주어야합니다. BFS를 이용해 각각의 섬에 인덱스를 부여해 구별하여 줍니다. 2. 그다음 이중포문으로 배열 전체를 돌면서 섬이 있는 칸으로 부터 상하좌우로 검사를 해줍니다. 검사는 재귀함수를 통..

티스토리툴바