Algorithm/graph

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/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 풀이 과정 문제 해결의 흐름 main 함수에서 무한루프를 돌자. 무한루프 속 이차원 배열을 돌며 population_map[i][j]의 연합국이 존재하는지 bfs로 탐색해본다. (이차원 배열을 전부 돌았지만 연합국을 찾지 못했다면 무한루프를 break하자) 연합국을 찾았다면 queue에 연합국의 행, 열을 넣고 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) 입력..

1. 문제 설명 링크 : https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 2. 풀이 과정 문제 해결의 흐름 7569 토마토 문제와 매우 비슷한듯? 무한 루프를 통해 0 0 0이 입력될 때까지 입력 받도록 하자 ! (단, 무한 루프를 통해 여러 테스트케이스를 거치기에 입력 받을 때 초기화는 필수다!) 시작 지점부터 6방향을 탐색하며 방문하지 않았고 막힌 곳(#)이 아니라면 이동하자! (막힌 곳이 아니라면 도착지점 E이거나 지나갈 수 있는 곳 .이다) ..

1. 문제 설명 링크 : https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 2. 풀이 과정 문제 해결의 흐름 입력 받은 배열을 이중for문을 돌며 각 국의 국력을 구한다. bfs를 통해 각 국의 병사 수를 구해 국력을 계산하자. 나의 코드 #include #include #include #include using namespace std; int N, M; char battleground[101][101]; bool vi..

1. 문제 설명 링크 : https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 2. 풀이 과정 문제 해결의 흐름 안전거리 : 현재 위치한 칸과 가장 가까운 아기 상어와의 거리 아기상어(1)를 찾는 것이 목표이기에 대각선 방향까지 포함한 8방향 탐색을 이어나가며 아기 상어를 찾자! 나의 코드 #include #include using namespace std; int N, M; int shark_map[51][51] = {..

1. 문제 설명 링크 : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 풀이 과정 문제 해결의 흐름 맵의 정보를 입력 받은 배열(land)를 기준으로 시작점은 land[0][0], 도착점은 land[N-1][M-1]일 것이다. 벽을 한 번만 부술 수 있으므로 다음의 기준으로 bfs를 구현하면 어떨까? (1) 다음 칸이 벽이고 벽을 부술 수 있다면? 벽을 뚫고 방문처리 (2) 다음 칸이 벽이 아니고 아직 방문하지 ..