백준

1. 문제 설명문제 링크 : https://www.acmicpc.net/problem/31796부산대학교 2024 pnup div1 / div2 기출문제 2. 풀이 과정문제 해결의 흐름입력 받을 때 바이러스 위치들을 전부 queue에 저장하자bfs 구현 q_virus와 q_building, 둘 중 하나가 빌 때까지 bfs 탐색이 이루어진다.Tg의 시간동안 virus가 감염시키는 것이 building이 완전히 감염되는 것보다 우선시되어야 한다. virus의 상하좌우에 building이 위치해 있다면 해당 building은 감염되었기에 q_building에 push해주자virus의 상하좌우에 안전지역이 위치해 있다면 해당 안전지역은 감염되어 virus가 되었기에 q_viurs에 push해주자q_buildin..

1. 문제 설명링크 : https://www.acmicpc.net/problem/94662. 풀이 과정문제 해결의 흐름 백준 '2668 숫자고르기'와 비슷하다고 생각했는데 많이 다른 거 같다 ㅠㅠ...이 문제의 키포인트는 '사이클을 완성할 때까지 탐색하다가 사이클을 이루는 요소들 골라주기'이다.  사이클을 완성시키는 경우는 어떤 것이 있을까? 예를 들어 아래의 경우 1 -> 4 -> 7 -> 6 -> 4 와 같이 사이클을 형성한다. 1로 시작해서 4로 끝났는데 뭔 사이클이냐?라고 생각할 수도 있다. 하지만 4 -> 7 -> 6 -> 4의 사이클을 이룬다! 따라서 이와 같이 사이클을 이루는 경우 탐색을 멈추고 사이클을 이루는 숫자들을 백트래킹해주자! 12345674137346 나의 코드 #include #..

1. 문제 설명링크 : https://www.acmicpc.net/problem/19872. 풀이 과정문제 해결의 흐름 좌측 상단에서부터 시작해서 상하좌우로 탐색하며 이동할 수 있는 최대 칸 수를 구해야하는 문제이다.dfs를 이용해 최대 칸 수를 완전 탐색으로 구해보자.이때, 알파벳 개수는 26개이므로 26개의 인덱스를 갖는 int형 배열을 통해 방문처리해주자.나의 코드 #include using namespace std;int dr[4] = {0,0,1,-1};int dc[4] = {1,-1,0,0};int R, C;int result_cnt = 0;char alphabet_map[20][20]; // 대문자 알파벳들을 입력 받을 이차원 배열int visited[26] = {}; // 전부 0으로 초..

1. 문제 설명링크 : https://www.acmicpc.net/problem/1525  2. 풀이 과정문제 해결의 흐름 문자열의 형태로 입력 받는다. ex) "1034567" 이차원 배열을 bfs를 통해 탐색한다. (queue에 push되는 값 : 0의 위치값과 퍼즐 위치 정보를 담은 문자열)  퍼즐을 이동시킨 형태 자체가 갱신값이므로 문자열로 치환하여 방문 처리해주자.이동하여 특정 위치에 도달하는 문제 : 이동 위치가 갱신 값연산하여 특정 값을 만드는 문제 : 연산 결과가 갱신 값 방문처리되는 문자열의 정수값은 1억이다. 그렇기에 int형 배열에 2억 개의 값을 초기화시킨다면 메모리 초과가 발생하므로 해시맵을 사용하였다. 나의 코드 #include #include #include // 해시맵 사용..

1. 문제 설명링크 : https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때www.acmicpc.net2. 풀이 과정문제 해결의 흐름  일단 단순하게 구현해보자. 이동할 때마다 1씩 증가되는 현재 이동 시간, curTime값을 통해 현재 동생의 위치 cur_K의 값을 갱신해주자.  예제로 17 5의 입력이 들어왔을 때를 생각해보자. 동생의 위치를 찾는 과정을 다음과 같다. 이때, 이전에 풀었던 숨바꼭질 1~4의 방식대로 방문처리해준다면 15 ..

1. 문제 설명링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때www.acmicpc.net2. 풀이 과정문제 해결의 흐름 ⭐️ bfs를 통해 이 문제를 푼다면 문제의 핵심은 '어쨌든 연산 횟수가 가장 적은 경우가 최단 시간이 된다'이다. 예를 들어 입력이 1 17이라면 아래와 같이 2가지 경우가 가장 적은 연산 횟수로 동생의 위치에 도달할 수 있는 방법일 것이다. ⭐️따라서 순간이동하는 경우 시간 경과가 0초라고 하더라도 가장 적..

1. 문제 설명링크 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때www.acmicpc.net2. 풀이 과정문제 해결의 흐름⭐️⭐️ 문제의 키포인트는 방문처리이다. 이전 문제인 '1697 숨바꼭질' 문제와 다른 방식으로 방문 처리해 주었다. 이전 문제는 단순히 '최단 시간'을 구하는 문제였기에 방문 배열에 시간을 저장해도 문제없었지만 이 문제는 최단 시간이 같은 다른 방법들을 모두 구해야 하기 때문이다. 그렇기에 queue에 {현재 ..

1. 문제 설명링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일www.acmicpc.net2. 풀이 과정문제 해결의 흐름 수빈이의 초기 위치는 N, 동생의 위치가 K로 주어졌을 때 수빈이가 처음 위치 N에서 +1칸, -1칸, *2칸 이동하며 동생의 위치까지 이동한다. bfs를 통해 동생의 위치까지 걸리는 최단 시간을 구해야 하므로 방문 배열에 시간을 저장해 주자!나의 코드 #include #include using namespace std;..

1. 문제 설명 링크 : https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 풀이 과정 문제 해결의 흐름 입력받을 때 일반인과 적록색약인 사람이 보는 구역 배열을 다르게 설정하자. 이중for문을 통해 방문처리되지 않은 값에 대해 bfs로 구역을 탐색하며 구역 수를 구하자. 나의 코드 // // 1. 입력 받을 떄 일반인과 적록색약인 사람이 보는 구역 배열을 다르게 설정하자. // 2. bfs를 통해 현재 행의 구역을 전부 방문 처리하고..

1. 문제 설명 링크 : https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 2. 풀이 과정 문제 해결의 흐름 문제 이해를 위해 예제를 직접 풀어보았다. [화면 속 임티 개수][클립보드 속 임티 개수] (1) 입력 : 2 [1][1] -> [2][1] (2) 입력 : 4 [1][1] -> [2][1] -> [2][2] -> [4][2] (3) 입력 : 6 [1][1] -> [2][1] -> [2][2] -> [4][2] -> [6][2] (4) 입력..