본문 바로가기

백준

 (49)
[ 백준 2573 ] 빙산 (C++) BFS 풀이 # 문제링크 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS 돌리면서 0 만나면 map에 -1 씩 해주고, 0이 아니면 queue 에 넣어서 계속 돌려주면 된다. 그렇게 한 덩이가 2개 이상이면 return 해주면 된다! # 제출 코드 #include #include #include using namespace std; int N, M; int map[300][300]; void input() { scanf("%d %d", &N, &M); for..
[ 백준 12886 ] 돌 그룹 (C++) # 문제링크 www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net 10 15 35 나, 15 10 35 나, 35 10 15나,,,, 같은 숫자 구성이다. 어차피 같은 숫자 구성인데 각각 진행시켜 줄 필요가 없다. 세 수를 오름차순으로 정렬해서 체크를 재주면 visited[500][500][500] 에 체크를 다 해줄 수 있다. 세 수의 비교 코드,, C언어 배울 때 if else 문 chapter 에서 국룰이었는데.. 그 때 생각하며 if else 를 열씸히..
[ 백준 19238 ] 스타트 택시 # 문제링크 www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 그 아기상어 문제를 풀고 난 뒤부터, 대부분 BFS 문제가 아기상어 문제처럼 보인다. 이것도 BFS로 손님 찾고 visit 초기화, BFS로 목적지 데려다주고 visit 초기화. 이런 식으로 진행된다. 손님을 찾는 BFS에서 손님 번호를 return 해야 하는데, 동시에 손님까지 간 거리도 return 해주고 싶었다. 왜냐면 solve 함수에서 taxi 관련 ..
[ 백준 9207 ] 페그 솔리테어 (C++) # 문제링크 www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다. www.acmicpc.net 이 문제를 처음 봤을 때는 왜이렇게 어렵게 생각했는지 모르겠다. ㅎㅎㅎ 처음 봤을 때는 저 말들을 어떻게 움직여줘야하지? 그냥 무작위로 다 움직이면 되나? 저 말들의 위치값을 받아두어야 하나? 한 번 움직이면 그 다음은 어떡하지? ... 뭔가 정리가 안되었다. 그냥 for 문 돌면서 말의 위치를 찾아서, 말이 이동 가능한 모든 경우의 수로 돌려보면 되는 문제였다. 근데 맵이 또 계속 달라지는데 어떻게 하지? 원본을 복사해뒀다가 한번 시뮬레이션을 하고 다시..
[ 백준 11562 ] 백양로 브레이크 # 문제링크 www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 처음에는 하나하나 BFS로 구했다. start 에서 end 까지 queue로 돌려가면서 최적의 거리를 찾았는데, 그렇게 하면 런타임에러가 난다. 그래서 검색해보니 다들 플로이드 와샬 방법으로 풀고있었다. 플로이드 와샬 방법은 모든 노드에서 모든 노드로 가는 최단거리를 정리할 수 있는 방법이다. start 노드에서 end 노드를 가는데, 중간에 어떤 노드를 들러서 갔을 때 더 좋은 결과가 나오면 갱..
[ 백준 17281 ] ⚾ 야구 구현 문제 # 문제링크 www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net DFS로 타자들의 순서를 정하고, 시뮬레이션을 돌려주었습니다. 그냥 뭐 생각할 것도 없고, if 문 여러 개 해서 조건만 맞추어서 돌려주었습니다. 시뮬레이션 문제는 진짜 문제 꼼꼼하게 읽고 그대로! 코드로 구현하는 게 중요한 거 같아요.. # 제출 코드 #include using namespace std; int N; int order[10]; int map[51][10]; bool chk[10]; in..
[백준 9205] 맥주 마시면서 걸어가기 (C++) DFS, BFS 풀이 # 문제링크 www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 이걸 첨에는 현재 좌표부터 1000m 거리 이내에 있으면 다 해보면 된다고 생각해서 DFS로 짰는데 시간초과가 났다. 사실 편의점의 갯수 n 이 100이니까 그냥 100개의 노드에서 DFS를 돌리면 시간초과는 당연한 결과다. 좌표값들을 정렬한다음에 우선순위로 하면 되지 않을까? 이런 생각도 했었는데, 잘못된 방법이었다. 결론 먼저 말하면, BFS로 풀거나, DFS로 풀때는 이미 방문한 노드를 ..
[백준 11967] 불켜기 (C++) BFS풀이 # 문제링크 www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net vector[][]를 만들어서 (x,y)좌표에 있는 스위치 위치를 push 해주었다. (1,1) 좌표부터 시작해서, 1) 좌표에 있는 스위치 불 켜기 2) 불을 새로 켰으면, 해당 위치부터 다시 BFS 돌리기위해서 visited와 queue 초기화 3) 네 방향으로 탐색하면서 불 켜져있는 곳으로 이동 이렇게 진행해줬는데, 한 번 스위치를 켰으면 ..

티스토리툴바