문제 문제 이해하기 여타 다른 문제와 입력값이 좀 다른데 다른 문제는 보통 graph matrix를 제시하고 1,0으로 vertex가 존재하는지 존재하지 않는지를 표현한다면 이 문제는 adjacecy matrix를 아예 입력값으로 제시한다. 때문에 다음과 같이 해석했다. (0)번 노드 기준 (1)번 노드 기준 (2)번 노드는 아무런 노드와도 연결되지 않았다. (2번 행 또는 열에서 자기 자신을 제외한 모든 원소 0) (3)번 노드 기준 따라서 위와 같은 4*4 인접 행렬이 주어졌을때 return 값 (그래프 수)는 2가된다. 해결 방법 방문 여부를 keep하는 visited[]행렬 대신 BFS로 방문하며 방문했던 노드의 자리를 0값으로 대치하여 모든 행렬의 원소가 0이될 때까지 BFS의 호출 수를 증가시..

문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해결 방법 행렬에 1로 되어있는 영역 (Graph) 갯수를 구하는 문제 BFS로 풀이한다. 노드간 연결을 수행할 때 양방향으로 해야하는지 단방향으로 해도 되는지 판단한다. 연결 대상 탐색은 우-하방향으로 하고 연결은 양방향 (우-좌, 하-상) 다 수행한다. 구현 [OrganicCabbage.kt] [main.kt]

문제 아이디어 총 단지수 == Graph 갯수 단지 내 집의 수 == Graph 내 노드(Vertex) 수 출력으로 요구하는 값만 봐고 DFS & BFS가 떠올랐다. 총 단지수 => main 에서 DFS 호출 수 단지 내 집의 수 => 한 DFS 내 재귀 호출 수 그래프 연결작업 => 행렬 전체를 돌며 '오른쪽, 아래'로 연결된 [행번호,열번호] 양방향 연결 리스트 추가 약간 헷갈렸던 것이 단지 내 집의 수 (DFS내 재귀 호출 수 카운트) 하는 부분이었다. DFS 코드 // main에서 마지막 argument로 DFS 호출 횟수를 keep하는 변수를 넘겨서 fun dfs (rowIndex: Int, colIndex: Int, callCount: Int) { //start vertex 는 0,0 가정 상..

문제 아이디어 정점, 간선 단어를 보자마자 '그래프'? 연결 요소 == 이어진 그래프를 의미한다. BFS or DFS를 떠올린다. 나는 BFS를 선택했다. 모든 노드(정점) 목록을 원소로 갖는 집합(Set)을 두고 한 번의 BFS마다 생기는 그래프를 전체 집합에서 제외시키는 방식으로 풀이했다. (전체 집합이 공집합이 될 때까지 Loop) 실수 undirected graph (무방향 그래프) 인것을 확인하지 않고 단방향 연결 리스트로만 체크하다가 틀려버렸다. 구현 [Graph.kt] import java.util.* import kotlin.collections.ArrayList class Graph(private val vertexNumber: Int) { val vertexSet : Set = (1 ...

문제 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 해결 방법 (1) 키패드간 거리가 '직선'이 아니라 상하좌우로 제한됨 -> X,Y 좌표계 도입! (2) [1,4,7]-> L, [3,6,9] -> R 고정이고 [2,5,8,0] 만 거리 계산이 필요함. // 거리가 같다면 hand 값 따지기 (3) 입력값은 모두 '숫자'지만 초기 왼,오른손은 '*', '#' character -> 어차피 정수로 변..

해싱 정의 키(key) 값에 직접 산술 연산을 적용하여 해시 테이블 주소를 통해 값(Value)에 접근하는 것 해시 테이블 (Hash Table) key 값의 연산에 의해 직접 접근이 가능한 자료구조 Dictionary == Map == Table 사전(Dictionary) 자료구조는 Key - Value를 갖는 자료구조로 오로지 키에 의해 값에 접근한다. (키가 정렬되었는지 여부는 구현시 결정 가능하다.) // 별로 중요하지 않다. ex) 사람 이름(key) - 전화번호(Value) 필수 연산은 다음과 같다. Insert Delete Search 이런 사전 자료구조 (Dictionary)를 효율적으로 구현하기 위해 해시 알고리즘을 적용한다. 해시 함수 키를 입력하여 해시 주소를 얻어낸다. 해시 주소는 ..