BFS

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/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/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) 다음 칸이 벽이 아니고 아직 방문하지 ..