c++/Baekjoon Online (38) 썸네일형 리스트형 백준 19237 : 어른 상어 C++ www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 풀이 1. 상어는 일단 shark라는 struct 만들어서 관리 -> 생존 여부 -> 현재 위치, 방향 -> 방향 우선순위들 2. map은 두개만들어서 관리 1) 상어들 2) 채취 정보 -> 누가 남겼는지, 몇턴 남았는지 3. 입력 다 받고 while문 돌린다. 탈출하는건 두가지! 1) 상어가 1번만 남음 2) 1000 이상! // 초과 아니다!!!!!!!!!! if.. 백준 19238 : 스타트 택시 c++ www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 전체 풀이 1. 택시를 taxi라는 struct 하나 만들고 그걸로 관리 2. 손님을 지금 위치랑 목적지 함께 저장해서 vector에 저장해둠 -> 후에 이 벡터가 다 비면 모든 손님 다 대려다줬다는거임 3. while문 돌리기 1) 처음에 택시에서 제일 위치 가깝고, 행 제일 작고, 열 제일 작은놈 찾음 2) 택시 거기로 이동 시키고 연료도 그만큼 깎음 - 가다가 연료 .. 백준 17142 c++ : 연구소 3 www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 고생한 포인트 1. 모두 활성화 시키는게 아니라 모두 바이러스로 채워야한다는 포인트를 제대로 못봤다!! -> 무슨 뜻이냐, 2는 남아있어도 되고 0만 없으면 된다!! -> 요런 경우 2. 시간초과로 고생했다. -> while문으로 BFS 레벨 한번마다 0이 남아있나 없나 여부를 확인했더니 시간초과가 떠버리더라 -> 0찾는거를 그냥 while문 밖으로 뺴면 while 문안에서 1과 2만 남는 경우를 캐치를 못하더라 3. .. 백준 1726 : 로봇 c++ www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 �� www.acmicpc.net 풀이겸 후기 1. 다른 BFS랑 다르게 추가로 생각해야되는 부분이 쫌 많았다 1) 그냥 기존 깊이에따라 cnt 할때랑 다르게 방향전환 을 고려해야되서 평소의 4방향 좌표 변환 전에 cnt를 미리 정해두는 방식을 쓸 수 없었다 -> struct로 묶어서 queue에 삽입 2) 각 좌표별로 바라보는 방향에 따른 visited 배열을 관리해야됬다 -> int visited[100][100][5]; 3) 여러방향에서 하나의.. 백준 11559 : Puyo Puyo c++ www.acmicpc.net/problem/11559 후기 겸 풀이 1. 생각보다 쉬운 문제다 구현만 잘하면 된다 2. 한 루프당 부셔질수 있는 블록들 체크 -> (부술수 있는게 없으면 게임 종료) -> 부셔질 블록들 제거 -> 부셔지고 남은 자리 채우기 반복 #include #include #include #include using namespace std; char map[12][6];// 뿌요뿌요 int check[12][6] = { 0, }; int visited[12][6] = { 0, }; vector team; int d_r[4] = { 1,-1,0,0 }; int d_c[4] = { 0,0,1,-1 }; bool break_possible() { for (int i = 0; i < 12; .. 백준 17244 : 아맞다우산 c++ www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 후기 1. 완벽하다고 생각해도 틀리면 극단적인 예시를 생각하자!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 2. 물건 하나도 없는 경우 생각안해서 런타임으로 진짜 1시간은 코드 째려본듯 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 풀이 1. 순열로 물건 집을 순서 정한다 2. 시작점 -> 물건들 -> 문 이렇게 거리 각각 구해서 더함 3. 거리 구하는건 언제나 하는 BFS -> 조금 특이하게 벽으로 둘러쌓여있어서 .. 백준 2206 : 벽 부수고 이동하기 C++ https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 후기겸 풀이 1. 처음에 입력받을때 map[i][j]가 1인 좌표들을 wall 이라는 vector로 만들고, 순서대로 하나씩 벽 없애고 BFS 돌리니까 바로 시간초과 뜨더라....ㅎ 2. 그래서 구글링으로 벽 부순상태인지 아닌지 확인용 flag 추가하는 풀이 확인! -> visited도 벽을 부순 상태랑 안부순 상태 구분! -> int visit[1000][1000][.. 백준 2146 : 다리만들기 C++ www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 1. 섬들 다 label링 -> 입력받을때 -1로 변환시키고 1부터 순서대로 label링 하면 편하드라 2. 각 섬별로 다른 섬에 지을 수 있는 다리 길이 중 최소값들 구하고 answer랑 비교 -> 처음에 섬 좌표 몽땅 queue에 집어놓고, queue 크기로 조절하면서 한단계씩 BFS!! -> 섬과 섬 사이가 n칸 떨어져 있으며 길이 n-1짜리 다리 놓으면 됨!!! (이거 때문에 헷갈려서 고생했으요) #in.. 이전 1 2 3 4 5 다음
