tony9402

백준 4179 불! 이 문제는 불이랑 거의 같은 문제라고 볼 수 있다.(이 문제를 풀면서 다시 처음부터 짰기 때문에 풀이는 살짝 느낌이 다를 것이다. 불이랑 다른건 상근(@)이가 아니라 지훈(J)이로 바뀌었고 불(*)은 불(F)로 바뀌었다. 풀이는 이전 포스트에서 간단히 설명을 올렸으니 저 곳에서 한번 보면 될 것이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include#include#include#include using namespace std; queue q;queue fire;char vmap[10..

백준 5427 불 이 문제는 상근(@)이가 안전하게 맵 밖으로 나가면 된다. 문제를 보면 불(*)이 붙으려는 칸으로 이동할 수 없다고 한다. 이를 알고리즘으로 해결하기 위해서는 불부터 이동시키고 그다음 상근이를 이동시키면 된다. 일단 먼저 맵의 정보를 읽으면서 불의 위치와 상근이의 위치를 각각 큐에 넣는다. 상근이의 위치가 들어 있는 큐의 크기가 0일 때까지 불을 한칸씩 이동시키고 상근이의 위치를 한 칸씩 이동시키면 된다. 이를 반복하다가 상근이가 맵 밖으로 나간다면 상근이가 이동한 횟수를 출력하면 되고 상근이의 위치가 담긴 큐의 크기가 0일 때까지 반복하는데 상근이가 맵 밖으로 못나갔으면 IMPOSSIBLE을 출력하면 된다. 1234567891011121314151617181920212223242526..

백준 2178 미로탐색 이 문제는 (1,1)부터 시작해 (N,M)로 가는 길 중 가장 짧게 갈 수 있는 경로를 찾는 것이다. 최단 경로를 구하는 문제는 대부분 BFS로 푸는 문제이다. 따라서 이 문제도 BFS로 푸는 문제이다. BFS는 queue를 이용하는데 queue에서 pop할때 도착 지점의 좌표가 나올때까지 하면 된다.문제에 길은 무조건 있다고 하니깐 그냥 없을 경우를 생각하지 않고 계속 push하고 pop을 하면 된다. 1. pair가 있다는 걸 몰랐을 때 짠 소스(queue에 대해서 독학 했을 때...) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585..

오랜만에 에듀코포가 있어 해보게 되었다. 너무 오랜만이라 그런지 문제를 해석해야하는데 해석도 안되고 문제를 읽기도 싫어서 대충 예제를 보고 풀려고 했지만 A번은 1시간 동안 안 풀려서 B -> A -> C로 풀었더니 1시간이 훌쩍 지나가버렸다. A번은 두 문자의 차이가 2 또는 0(같은것)인것을 보면 되는 단순한 문제였는데 문제를 안읽어 제출을 많이 했다. B번은 대충 배열 쓰면 되겠지하고 봤더니 n의 범위가 최대 10^9여서 멍 때리다가 규칙을 찾고 대충 제출 했지만 케이스 n == 2일때만 틀려서 2일땐 그냥 노가다로 if문 떡칠을 하였다. C번은 처음에 O(n^2)로 풀었는데 TLE가 떠서 O(n) 풀이가 있을꺼 같아 살짝 그리디하게 짜봤더니 AC가 떳다. 시간 복잡도 A번 -> O(N)B번 -> ..

백준 2606 바이러스 이 문제는 (매우..?) 쉬운 문제이다. 알고리즘 분류에는 플로이드 와샬로 되어있는데 이건 단순히 DFS로 풀린다.입력 받는 데이터를 이용해 인접리스트를 만들고 컴퓨터 1번에서 DFS를 한 번 돌리면 답이 나온다. 1234567891011121314151617181920212223242526272829303132333435363738#include#include using namespace std; vector map;bool visit[101] = { false };int computer_num, ans = 0; void dfs(int x){ ans++; visit[x] = true; for (int k = 0; k

백준 10026 적록색약 이 문제는 DFS 또는 BFS로 풀 수 있는 문제지만 둘 중에 하나로 두 번 돌려야 되는 문제이다. (두가지 풀이로 쓰기 귀찮아서 BFS 풀이만 올리겠다.) 먼저 BFS로 한 바퀴 돌릴 때 G인 곳을 R로 바꾸면서(R을 G로 바꿔도 상관없다) 색상에 의해 몇 구역으로 나뉘는지 체크를 하고 또 다시 BFS로 한 바퀴 돌리면 풀리는 단순한 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include#include#include u..

백준 1012번 유기농 배추 이 문제는 백준 2667번 단지번호붙이기와 거의 같은 문제이다.단지번호붙이기와 다른점은 단지마다 넓이를 구해야하고, 유기농 배추는 단지의 갯수만 구하면 되는 문제이다. 1. BFS를 이용한 풀이 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include#include using namespace std; queue q;int dx[] = { -1,1,0,0 };int dy[] = { 0,0,-1,1 };int map[55][55] = { 0 }; int main(){ int T; int m, n, k; int x, y; int ans; ..

백준 2667번 단지번호 붙이기 이 문제는 BFS로 풀어도 되고 DFS로 풀어도 되는 문제이다. 아는 사람도 있을 것이고 모르는 사람도 있을 수도 있으니 입력부분에서 하나 집고 가자면 예제 입력 부분을 보면 0110100 이런식으로 숫자가 붙어서 들어오는데 scanf를 잘 사용하면 숫자 한개씩 입력 받게 가능하다. (어떤 사람은 이걸 몰라 문자열로 입력 받아 처리하는 경우가 있었다. 이 문제에선 큰 상관이 없긴 하지만 다른 문제에서 쓰일 때가 있을 것이다.) 1234567for(int i=0;i

다음 글 부터는 백준 DFS/BFS 관련 문제를 풀이 하는 글을 올릴 예정이다. 일단 백준에 있는 문제들 중에서 DFS/BFS 문제를 나열해보자 boj.kr/1260 - DFS와 BFSboj.kr/2178 - 미로 탐색boj.kr/7576 - 토마토(2차원)boj.kr/7569 - 토마토(3차원)boj.kr/2667 - 단지번호붙이기boj.kr/1012 - 유기농 배추boj.kr/2583 - 영역 구하기boj.kr/2468 - 안전 영역boj.kr/14502 - 연구소boj.kr/2589 - 보물섬boj.kr/10026 - 적록색약boj.kr/3055 - 탈출boj.kr/2206 - 벽 부수고 이동하기boj.kr/14442 - 벽 부수고 이동하기 2boj.kr/1600 - 말이 되고픈 원숭이boj.kr/..

보호되어 있는 글입니다.