문제https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이문제를 읽으면 Flood fill을 사용하는 문제임을 알 수 있다. 잠시 Flood fill을 알아보면,Flood fill이란? 2차원 배열(혹은 다차원 배열)에서 주어진 시작점과 연결된 영역 전체를 찾아서 특정 값(색상 등)으로 바꾸는 알고리즘 Flood fill을 이용한 BFS의 기본적인 예제 문제이다. (0, 0)에서 (n-1, m-1)까지의 최단 경로를 찾아야 한다. 프로그래머스 특성상 다음의 처리만 잘 해주면 된다.방문할 수 없는 경우 -..
![[BOJ] 2178 미로 탐색 (C++)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FbHjX68%2FbtsPbMdKtMP%2FAAAAAAAAAAAAAAAAAAAAAJxBpkd2f1FnBVWRQ7P0AUqB2MImLpI2XJFNoQSAhQ63%2Fimg.png%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1756652399%26allow_ip%3D%26allow_referer%3D%26signature%3DcvhfTUosMtAcEzKIxZTXnAYo79s%253D)
문제https://www.acmicpc.net/problem/2178 풀이사실 이 문제는 BFS의 기본 문제입니다. BFS가 처음이신 분들은 이 문제를 예제삼아 알고리즘의 정당성을 공부하면 좋습니다. 행렬에서 특정 점까지의 최단 경로를 구하는 문제이다. BFS를 이용하면 특정 점까지의 최단 경로가 보장되므로 방문 가능한 좌표들을 중심으로 BFS를 수행하면 된다.que에 {0, 0}을 추가하여 시작점으로 설정상하좌우를 확인하며 방문 가능한 경우(아래 조건 만족하는 경우)에 대해서만 방문 진행방문 체크가 안되어 있어야 함값이 0이 아니어야 함범위 안에 존재해야 함que에서 꺼낸 현재 좌표가 {N-1, M-1}일 때까지 반복한다. 코드#include#include#define IN(Y, X) (Y = 0 &&..
1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 풀이 아이디어 알고리즘 코드 #include #include #include #define F first #define S second #define IN(Y, X) Y >= 0 && Y = 0 && X < N using namespace std; queue q; int dy[4] = {0, 1, 0, -1}; int dx[4] = {1, 0, -1, 0}..
#include #include #include #include #define F first #define S second #define IN(Y, X) Y >=0 && Y =0 && X < M using namespace std; int N, M, cheese, board[100][100]; bool visit[100][100]; queue q; vector melt; int dy[4] = { 0, 1, 0, -1 }; int dx[4] = { 1, 0, -1, 0 }; void BFS(int y, int x) { visit[y][x] = true; q.push({ y, x }); while (!q.empty()) { pair front = { q.front().F, q.front()..