모항이코딩한다

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.28 섬의 개수를 저장할 int형 변수 answer을 선언하고 0으로 초기화한다. 지도의 모든 칸에 대하여, 아직 방문한 적이 없는 섬 땅 부분이 발견될 때마다 answer를 1 증가시키고, 그 땅 좌표를 시작으로 dfs를 돌린다. dfs를 돌리면서 거쳐가는 모든 땅은 방문했다고 표시해준다. 코드 Java(2022.05.28) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static boolean[][] map;//지도정보 stati..

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.28 방문한 적 없는 배추가 발견될 때마다 필요한 지렁이 수를 1 증가시키고, 그 배추를 시작으로 인접한 배추들을 모두 방문해주면 된다. 다시 말하자면 정답을 저장할 int형 변수 answer을 선언한 뒤 0으로 초기화한다. 그 후 밭의 모든 칸에 대하여, (이번 칸이 배추임) AND (이번 칸을 방문한 적 없음) 이 true일 경우 answer을 1 증가시키고, 이번 칸에 대하여 dfs를 돌아준다. 코드 Java(2022.05.28) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringToke..

풀이방법 및 문제점 2022.05.28 자바로 시간초과를 안 내기가 매우 매우 어려운 문제다. 난 최선을 다했다...따흐흑 다른 언어로 시도한 사람들은 나와 똑같은 알고리즘으로도 성공했다. 자바로 시도한 다른 사람들은 동일한 코드를 여러 번 제출했더니 한 번은 시간초과, 한 번은 통과가 된다고 한다ㅋㅋㅋㅋㅋㅋㅋㅋ굉장히 빡빡한가 보다. 시간을 줄일 기발한 알고리즘이 떠오르지 않는 한, C++ 또는 Python으로 나중에 도전하는 것이 낫겠다. 코드 Java(2022.05.28) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import j..

풀이방법 및 문제점 2022.05.27 지금까지 몇 개의 노드를 방문해왔는지 저장하는 변수 num을 전역변수로 설정하지 않고 재귀 시마다 넘겨주는 변수로 선언하였더니 틀린 답이 도출되었다. 이 점을 기억하기 위해 오답노트에 적는다. 틀렸던 이유는, 새로 방문하는 노드를 만날 때 dfs 함수 내에서 1 증가시켜주었던 num의 값이, 재귀가 끝나 이전 노드로 거슬러올라갈 때 다시 1씩 줄어든다는 데 있었다. 이것을 알아채는 것에는 백준의 질문 게시판에 있던 다음의 테스트케이스가 도움이 되었다. 6 7 1 1 6 1 2 2 6 2 3 2 4 3 5 4 5 1 -> 2 -> 3 -> 4 -> 5 -> 6 위 소스는 아래와 같이 나오네요. 1 2 3 5 4 3 내 코드에서도 똑같은 오답이 나와서 왜 그럴까를 고민..

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.07 오답노트 #24479 : 알고리즘 수업 - 깊이 우선 탐색 1 풀이방법 및 문제점 2022.05.27 지금까지 몇 개의 노드를 방문해왔는지 저장하는 변수 num을 전역변수로 설정하지 않고 재귀 시마다 넘겨주는 변수로 선언하였더니 틀린 답이 도출되었다. 이 점을 blowupmomo.tistory.com 그냥 시작 노드에 대하여 깊이우선탐색을 해주면 된다. 단! 한 정점에 여러 노드가 연결되어있을 경우 그 노드들을 오름차순으로 방문한다. 따라서 인접 리스트의 요소들이 오름차순으로 정렬되어있어야 한다. 이 점 때문에 나는 요소들을 자동으로 오름차순 정렬시켜주는 TreeSet를 사용했다. 코드 Java(2022.05.27) import java.io..

풀이방법 사용된 것: 깊이우선탐색 2022.05.25 모든 정점에 1 혹은 2 중에 하나의 번호를 부여해야 한다고 하자. 인접한 두 정점이 같은 번호를 부여받는 일 없이 모든 정점에 1 혹은 2를 부여할 수 있다면 그 그래프는 이분 그래프이다. 더보기 여러 칸으로 나누어진 그림을 2가지 색으로만 색칠하되, 인접한 칸끼리는 색이 겹치지 않도록 하는 색칠 수수께끼와 비슷하다고 보면 된다. 이 원리를 이용하여 이 문제를 풀 수 있다. 그 방법은 다음과 같다. 정점들을 깊이우선탐색 또는 너비우선탐색하면서, 다음 정점으로 넘어갈 때마다 이전에 방문했던 정점과 다른 번호를 부여한다. 그 후 정점들을 검사해보았을 때, 인접한 두 정점이 같은 번호를 부여받은 경우가 하나도 없다면 이 그래프는 이분 그래프이다. 코드 J..

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.25 그래프 탐색을 통해 각 영역에 속한 칸들을 탐색하고 양과 늑대의 마릿수를 세는 문제이다. 나는 깊이우선탐색을 사용하였다. 알고리즘은 다음과 같다. 마당의 특정 한 칸을 시작으로 깊이우선탐색을 하면, 그 칸과 같은 영역에 속하는 모든 칸을 한 번씩 방문할 수 있다. 이 과정에서 그 영역의 양과 늑대의 마릿수를 세어주면 된다. 이러한 과정을 마당의 모든 칸에 대하여 수행하면 문제가 해결된다. 다음은 코드 설명이다. 사용된 전역변수는 다음과 같다. static int r, c;//마당의 크기(r은 행, c는 열 개수) static char[][] map;//마당 지도 static boolean[][] visited;//방문여부 판별 static i..

풀이방법 사용된 것: 분할 정복 재귀 2022.05.19 전체가 '-'로만 채워진 문자열을 먼저 만들고, 함수 f가 특정 부분을 지우는 식으로 해결한다. 재귀적으로 정의된 함수 f는 다음과 같이 동작한다. 주어진 문자열을 세 부분으로 동등하게 쪼갠다. 주어진 문자열의 가운데는 지운다. 주어진 문자열의 왼쪽과 오른쪽에 대하여는 재귀를 한다. 따라서 갈수록 더 짧은 부분에 대하여 재귀를 해나가게 된다. 주어진 문자열의 길이가 1이 되었을 때가 base case이다. 이때 재귀를 종료한다. 코드 Java(2022.05.19) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java..

풀이방법 사용된 것: ArrayList 2022.05.20 출력해야 하는 점의 x좌표와 y좌표는 세 번의 입력 중 단 한 번만 나온다. 두 번 나오는 값은 무시하고 딱 한 번 나온 x좌표와 딱 한 번 나온 y좌표를 출력하면 된다. ArrayList를 x좌표를 위한 것 하나, y좌표를 위한 것 하나를 만든다. 3개의 좌표값을 읽어오면서 처음 나온 값은 ArrayList에 저장을 하고 두 번째 나온 값은 ArrayList에서 지운다. 그럼 세 좌표값을 모두 읽은 후에는 각각의 ArrayList에 값이 하나씩만 남는다. 그 값들이 정답이다. 코드 Java(2022.05.20) import java.io.BufferedReader; import java.io.IOException; import java.io.I..

풀이방법 사용된 것: 분할 정복 재귀 2022.05.18 분할 정복 문제이고, 재귀적으로 정의된 함수를 사용한다. 사용된 전역변수는 char[][] print : 출력할 별 그림 이렇게 하나이다. 사용된 함수 star()의 구조를 간단히 설명하자면 다음과 같다. 함수 star() 개요 star()은 특정 영역에 대하여, 영역의 한 변의 길이가 3이라면 해당 영역에 3x3짜리 별 그림을 직접 찍고, 영역의 한 변의 길이가 3보다 크다면 재귀를 수행하는 함수이다. 매개변수 int row : star()에서 다룰 영역의 시작부분(가장 왼쪽 위 지점)의 열 좌표 int col : star()에서 다룰 영역의 시작부분(가장 왼쪽 위 지점)의 행 좌표 int len : star()에서 다룰 영역의 한 변의 길이 작..