조준화의 오류정정

BFS와 관련된 문제를 풀었다. 골드 3 이상 난이도의 문제는 아직 수월하게 풀지 못하는 것 같다. 그동안 BFS라 하면 그래프 탐색에서만 쓰인다고 생각했는데 오히려 아닌 느낌의 문제가 더 많았고 더 이상 BFS가 두렵지 않다. 지금의 방식처럼 한 주제를 공부하고 관련 문제를 계속 푸는 방식이 큰 도움이 된다. 마치 계단을 오르는 것처럼 한 주제를 공부할 때마다 문제풀이가 느는 게 느껴진다. 문제풀이는 지금의 방식에 만족하지만 이번에 우테코 지원서를 작성하면서 이대로 문제풀이만 공부해도 괜찮을까 라는 생각이 들었다. 얼른 프로젝트도 하고 싶고... 팀원 구하긴 힘들고... 일단 자바 언어 숙련도도 계속 발목을 잡으니 다시 복습하면서 자바로도 문제풀이를 해야겠다. JS, html, css 등 프런트 기초 ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 예제 6 4 0100 1110 1000 0000 0111 0000 15 4 4 0111 1111 1111 1110 ans : -1 처음에는 BFS를 하는데, dist를 pair로 해서 방문가능하지 판단할 때 if(dist.second) >= 2 continue; 이런 느낌으로 한 번 부수면 계속 그 사실을 기억하는 식으로 풀이를 짰다. 그러나 pair로 구현하면 구현이 굉..

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 2 7 3 1 3 7 3 4 6 8 1 2 3 4 5 6 7 8 ans : 3 0 처음에는 평범한 BFS를 사용한 O(n^2) 풀이를 떠올렸다. BFS를 이용해 자기 자신을 다시 만나면 사이클 안이라서 팀, 자기 자신이 아닌 방문한 곳을 만난다면 사이클 밖이라서 팀이 아닌 것으로 판단하였다. 그러나 시간초과에 걸려서 다른 풀이를 떠올려야 했다. 아래의 풀이는 O(n^2) 풀이이다. /** BFS 9466 텀 프로젝트 **/ #include #include #inclu..

BFS는 큐를 이용한 탐색의 한 방법으로, 너비 우선 탐색이다. 너비 우선 탐색이라고 하면 감이 잘 안 올 텐데, 알고리즘부터 보자. 큐에 시작점을 push 한다. 큐의 front를 저장해 두고 pop 한다. pop한 원소에 방문표시를 해둔다. 저장해 둔 원소의 상하좌우 중 방문가능한 원소를 큐에 집어넣는다. 큐가 빌 때까지 2~3을 반복한다. 이를 바탕으로 Flood Fill을 해보자. Flood Fill은 흔히 그림판에 있는 페인트 기능으로, 경계선을 기준으로 색을 일괄 변경하는 기능이다. 어떻게 구현하냐면, 어떤 칸의 상하좌우를 살펴보고 같은 색이라면 포함시키고, 아니라면 경계선으로 설정하는 느낌으로 구현하면 되는데 BFS를 사용하면 쉽게 구현할 수 있다. BFS의 구현은 거의 정석적으로 정해져 있..

4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 4 4 #### #JF# #..# #..# ans : 3 전에 푼 토마토 문제와 비슷한 느낌이지만 굉장히 다르다. 불과 지훈이가 동시에 BFS를 돌리면 될 것 같지만 사실 무조건 불부터 돌려야 한다. 같은 시간대에 불이 도달할 수 있으면 지훈이는 해당 칸에 못 가기 때문이다. 동시에 돌리는 것처럼 큐 한 개로 처리하면 우선순위를 고려하기 굉장히 번거롭고 오래 걸린다. 따라서 불부터 BFS를 돌리고, 지훈이 도착시간이 불보다 작으면 방문 가능한 칸..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 예제 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ans : 8 최단 경로를 보고 바로 BFS를 떠올렸다. 조금 다른 점은 토마토가 여러 개인 경우 동시에 여러 시작점에서 BFS를 시작해야 한다는 것이다. 토마토들 간의 우선순위는 없으니 간단하게 큐에 시작점을 모두 넣고 BFS를 돌리면 된다. 구현은 전에 푼 문제와 거의 똑같다. 조금 다른건 토마토가 없는 칸, 즉 다른 문제의 벽에 해당하는 칸만 ..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 예제(더 많은 예제는 링크에 있습니다.) 4 6 101111 101010 101011 111011 ans : 15 BFS의 가장 대표적인 문제 중 하나로, 최단경로 탐색 문제이다. 최단 경로가 왜 BFS냐면, 여러 갈래 길이 나왔을 때 마치 BFS처럼 너비 우선으로 길을 찾으면서 진행하기 때문이다. 최단경로가 나오면 BFS를 가장 먼저 고려해 보자. 기본적인 BFS 구현에서 visited 배열만 dist 배열로 바꿔서 거리를 표시해 주면 된다. dist의 모든 칸을 -1로 두고, BFS의 시작..

오늘은 재귀 공부를 끝내고 수식의 괄호쌍도 간단히 공부했다. 재귀 문제를 풀면서 아주 기본적이지만 놓치고 있었던 게 있었다. 다차원 배열을 초기화할 때 char star [23][23] = {' ', };와 같이 초기화하면 안 된다는 것과 잘 초기화된 다차원 문자형 배열을 for(int i=0; i

2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 예제 27 ans: *************************** * ** ** ** ** ** ** ** ** * *************************** *** ****** ****** *** * * * ** * * ** * * * *** ****** ****** *** *************************** * ** ** ** ** ** ** ** ** * *************************** ..

1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 예제 9 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 -1 0 1 -1 0 1 -1 0 -1 1 0 1 -1 0 1 -1 0 1 -1 1 0 -1 0 1 -1 ans: 10 12 11 문제의 규칙 자체가 분할 정복이다. 따라서 귀납적 사고를 통해 재귀 함수의 구조를 짜려했다. 귀납적..