안녕하세요. 이번 시간에는 클래스 중 조금 특별한 속성을 갖고 있는 추상 클래스(Abstract Class)와 자바에서 등장하는 인터페이스(Interface)에 대해서 알아보는 시간을 갖도록 하겠습니다.

추상클래스(Abstract Class)

이름부터가 아주 비호감입니다. 저는 추상이라는 단어를 무척이나 싫어하거든요.

뭔가 있는 듯 없는 듯하면서도.. 만질수 있을 듯 없을 듯하면서도.. 볼수 있을듯 없을 듯한 그 거시기한 거.. 그런건데

아주아주 간단히 말해서 추상메소드가 적어도 0개 있는 클래스가 추상클래스라고 합니다.

장난하냐? 그러지 마시고 일단 추상 메소드가 무엇인지 말씀 드리고 시작하겠습니다.

추상클래스는 메소드의 선언만 되어있을 뿐 정의는 되어있지 않은 것을 말합니다. 몸통이 없다는 것이죠.

몸통이 없이 메소드의 선언만 존재하는 것이 추상 메소드이며 추상 메소드를 0개 이상 갖는다면 추상클래스이다 라고 말할 수 있겠네요. 

0개 이상이라는 말은 추상메소드를 갖지 않아도 추상 클래스가 될 수 있다는  것인데, 이렇게 되면 보통의 클래스를 의미하기 때문에 보통은 한개 이상 추상 메소드를 갖는다면 추상 클래스라고 합니다.

아래와 같이 사용합니다. 우선 추상클래스를 정의하려거든 class앞에 abstract라는 키워드를 붙여줍니다.

추상메소드 역시 마찬가지입니다. abstract 키워드를 붙이고 메소드 구현부만 없으면 됩니다. 

abstract class AbstractClass{
	int x;
	public void NormalMethod() {}
	public abstract void AbstractMethod(); 
}

보통의 클래스와의 차이점은 객체를 직접생성할 수 없다는 점입니다.

그래서 이 추상 클래스를 상속받아 그 상속받은 클래스의 객체로 생성해야합니다. 또는 다형성의 성질을 이용할 수 있지요.

사용법은 아래의 코드와 같습니다.

abstract class Animal{
	public void seeFood() {
		System.out.println("내가 음식을 봤을 때");
	}
	abstract public void cry();
}

class Dog extends Animal{

	@Override
	public void cry() {
		System.out.println("왈!! 왈왈!! 왈왈~!!! 왈월워뤙왈!!! 멍멍!");
	}
	
}

class Cat extends Animal{

	@Override
	public void cry() {
		System.out.println("야옹~~ 옹옹오오오오오옹~~~~~~ 야오우오우오우옹~~~~");
	}
	
}
public class Main {

	public static void main(String[] args) {
		Animal dog=new Dog();
		dog.seeFood();
		dog.cry();
		
		System.out.println();
		
		Animal cat=new Cat();
		cat.seeFood();
		cat.cry();
	}
}

Animal을 상속받은 클래스 Dog와 Cat은 무조건 abstract의 메소드를 오버라이딩해주어야 합니다. 그렇지 않으면 Animal클래스를 상속할 수 없습니다.

결과는 어떻게 될까 예상이 되시나요?

여기서 추상클래스와 비슷한 인터페이스(Interface)를 소개합니다.

인터페이스(Interface)

인터페이스는 명세라고도 불리는데요. 추상클래스의 가장 극단적인 형태라고 보면 됩니다. 

인터페이스는 전부가 추상메소드로 이루어져 있습니다.

자신의 변수도 쓸수 없고 오로지 메소드의 선언만이 있어야합니다.

아래처럼 말이죠.

interface Interface {
	public void method1();
	public void method2();
}

마치 추상클래스로 표현하자면 이렇게 표현할 수도 있겠네요.

abstract class Interface{
	public abstract void method1(); 
	public abstract void method2(); 
}

인터페이스의 사용 예제는 아래와 같습니다.

interface Animal {
	public void cry();
	public void sleep();
}

class Dog implements Animal{

	@Override
	public void cry() {
		System.out.println("왈!! 왈왈!! 왈왈~!!! 왈월워뤙왈!!! 멍멍!");
	}
	@Override
	public void sleep() {
		System.out.println("자신의 집에서 잠을 잡니다.");
	}
	
}

class Cat implements Animal{

	@Override
	public void cry() {
		System.out.println("야옹~~ 옹옹오오오오오옹~~~~~~ 야오우오우오우옹~~~~");
	}
	@Override
	public void sleep() {
		System.out.println("집사 얼굴 위에서 잠을 잡니다.");
	}
	
}
public class Main {

	public static void main(String[] args) {
		Animal dog=new Dog();
		dog.cry();
		dog.sleep();
		
		System.out.println();
		
		Animal cat=new Cat();
		cat.cry();
		cat.sleep();
	}
}

Dog와 Cat은 Animal 인터페이스를 implements하고 있습니다. 근데, 이제까지 봐왔던 extends가 아니군요. 그 이유는 아래에서 설명하도록 하겠습니다.

결과는 이렇게 됩니다.

추상클래스 VS 인터페이스

한가지 중요한건 이 둘의 차이에 대해서 알아야합니다.

추상클래스는 역시 클래스입니다. 단독으로 객체를 생성할 수만 없지 나머지는 보통의 클래스처럼 생성자, 변수, 메소드를 갖고 있을 수 있습니다. 그렇기 때문에 자식 클래스에서는 변수나 구현된 메소드를 물려받기 때문에 상속(extends)받을 수 있는 것이죠.

인터페이스 역시 직접 객체를 생성할 수 없습니다. 구현되어야 할 메소드만 명시해 놓고 인터페이스를 받는 클래스는 그 인터페이스에 맞는 메소드를 구현해야합니다. 그렇기 때문에 implements(구현하다)라는 키워드로 인터페이스를 전달받을 수 있지요.

클래스와는 다르게 여러개의 인터페이스를 클래스가 구현할 수 있습니다. 클래스로 따지자면 다중상속과 비슷한 개념입니다.

자바는 다중상속을 지원하지 않지만 다중 인터페이스를 통한 상속은 지원하지요.

interface Calculator{
	public int sum(int a,int b);
	public int subtraction(int a,int b);
}

이제 왜 인터페이스는 implements를 써서 받고, 추상클래스는 extends를 써어 받는 지 차이점을 알겠죠?

다형성(Polymorphism)

다형성이라는 개념은 OOP에서 아주 중요한 개념이므로 모르면 OOP에 대해서 제대로 안다고 할 수 없는 개념입니다.

각 요소들이 여러 가지 자료형으로 표현될 수 있다는 것을 말하게 되는데, 반댓말로는 단형성이 있습니다. 한가지의 요소는 한가지의 형태로만 매칭된다는 것을 의미합니다.

음... 일단 모르겠어요.. 다형성이 정확히 무엇인지.

암튼 뭐.. 앞에 '다'라는 의미는 '많은 다(多)' 자가 아니겠어요?? 뭔가 여러가지 (자료)형을 말하는 것 같은데 클래스를 만들어가면서 알아보도록 하지요.

여기 People이라는 클래스가 있습니다. 아주 간단하게 정의한 클래스죠. 그 안에는 printInfo라는 멤버메소드가 있군요.

class People{
	
	public void printInfo() {
		System.out.println("나는 사람입니다.");
	}
}

People 클래스에서 printInfo를 호출하게 되면 지가 사람이라는 군요.

그 밑에 Man과 Woman 클래스는 People클래스를 상속합니다.

class Man extends People{}
class Woman extends People{}

이후 메인에서는 이 두 클래스를 객체로 만들어 printInfo를 호출합니다. 

public class Test {

	public static void main(String[] args) {
		Man man=new Man();
		Woman woman=new Woman();
		
		man.printInfo();
		System.out.println();
		woman.printInfo();
	}
}

이후 실행을 하게 되면 아래의 결과가 나오게 되겠죠.

두 클래스 Man과 Woman은 People이라는 클래스를 상속받았으므로 printInfo 호출시 People의 printInfo를 호출할 수 있다는 것, 뭐 놀랍지 않군요.

이제 이것을 토대로 다형성을 세세하게 알아보도록 합시다.

Woman, Man은 People이다

UML 다이어그램으로 본다면 위의 그림과 같을 겁니다.

Man과 Woman은 People이라는 클래스를 상속하기 때문이에요.

우리는 이 다이어그램을 이런 관점으로 한번 바라볼 수 있을까요?

현실 세계에서 이 다이어그램을 말로 풀어보아도 그 의미가 맞습니다.

그 반대는 어떨까요?

사람은 남자인가요? 아니면 사람은 여자인가요?

그렇지 않습니다. 사람은 남자인지, 여자인지 알 수가 없습니다.

그렇기 때문에 반대로 표현하면 모호해진다는 것을 알 수 있지요.

여기서 중요한 점은 Man은 People로 표현할 수 있고, Woman도 People로 표현할 수 있다는 것입니다.

이것이 다형성의 개념이 나오게 됩니다. Man과 Woman은 People이기 때문에 People이라는 자료형으로 받을 수 있습니다.

한번 확인해볼까요?

public class Test {

	public static void main(String[] args) {
		People people=new Man();
		
		people.printInfo();
		System.out.println();
		
		people=new Woman();
		people.printInfo();
		
	}
}

실행을 시켜서 확인해보면 위의 결과와 동일한 것을 알 수 있습니다. 

Man과 Woman은 People(부모클래스)로 받을 수 있다는 점을 기억하세요!

다형성과 오버라이딩

여기서 Man과 Woman은 printInfo를 물려받았고 오버라이딩(Overriding)할 수 있다는 것을 알고 있습니다.

그래서 저는 Man과 Woman의 printInfo를 그 클래스에 맞도록 오버라이딩하고 싶습니다. Man과 Woman 클래스를 다음과 같이 수정해보도록 하지요.

class Man extends People{
	@Override
	public void printInfo() {
		super.printInfo();
		System.out.println("그리고 나는 남자입니다.");
	}
	
}
class Woman extends People{
	@Override
	public void printInfo() {
		super.printInfo();
		System.out.println("그리고 나는 여자입니다.");
	}
}

그리고 실행해본다면 

오버라이딩된 printInfo를 호출한다는 것을 알 수 있습니다. 오...

다형성에서 People은 자식클래스에서 재정의된 메소드를 호출할 수 있다는 것입니다.

그렇다면 Woman과 Man에서 단독으로 정의한 메소드는 어떻게 될까요?

Man과 Woman클래스에서 다음과 같이 메소드를 추가해보도록 합시다.

class Man extends People{
	@Override
	public void printInfo() {
		super.printInfo();
		System.out.println("그리고 나는 남자입니다.");
	}
	
	public void enlist() {
                System.out.println("내일 군대를 갑니다.");
		System.out.println("충성!");
	}
	
}
class Woman extends People{
	@Override
	public void printInfo() {
		super.printInfo();
		System.out.println("그리고 나는 여자입니다.");
	}
	
	public void makeUp() {
                System.out.println("예뻐질 거랍니다.");
		System.out.println("톡톡 촵촵!");
	}
}

그리고 people.enlist를 호출하려한다면 호출이 되지 않습니다. 왜냐하면 People 형이기 때문이죠. People 클래스는 enlist라는 메소드를 갖지 않기 때문에 호출할 수 없습니다.

이런 경우에는 데이터 형에 맞게 캐스팅해주어서 사용해야합니다.

바로 아래처럼요.

public class Test {

	public static void main(String[] args) {
		People people=new Man();
		people.printInfo();
		((Man)people).enlist();
		
		System.out.println();
		
		people=new Woman();
		people.printInfo();
		((Woman)people).makeUp();
		
	}
}

왜 그런걸까요?

People은 자신을 상속한 클래스 중에서 어떤 매소드를 만들지, 어떤 멤버 변수를 만들어낼지 미리 알아낼 수 없기 때문이죠.

때문에 그 메소드가 있는 객체로 직접 캐스팅해주어서 매소드를 사용해야합니다.

이해를 돕기 위한 그림이 아래에 있습니다. People이라는 자료형이 사용가능한 메소드는 printInfo밖에 없습니다. 그래서 Man의 printInfo메소드를 사용할 수 있습니다. 

또한 new가 동적 메모리를 할당하는 역할을 하므로 Man이 실제 메모리에 잡히게 됩니다. 따라서 형변환을 Man으로 하는 것이 가능한 것이죠.

이와 같은 다형성은 어디에서 쓰일까요?

대표적으로 메소드에서 매개변수로 People을 상속하는 클래스를 받을때 사용할 수 있습니다. 

        public static void func(People people) {
		people.printInfo();
	}
	public static void main(String[] args) {
		Man man=new Man();
		Woman woman=new Woman();
		func(man);
		
		System.out.println();
		func(woman);
	}

func의 매개변수 people은 People의 객체이기 때문에 그것을 상속하는 모든 클래스를 받아 낼 수 있어요.

그래서 Object 객체로 모든 객체를 받을 수 있는 것도 바로 이러한 다형성의 속성때문입니다. 

또한 필요에 의해서는 instanceof 연산자를 사용해서 캐스팅할 수 있습니다.

        public static void func(People people) {
		people.printInfo();
		if(people instanceof Man) 
			((Man)people).enlist();
		if(people instanceof Woman)
			((Woman)people).makeUp();
		
	}
	public static void main(String[] args) {
		Man man=new Man();
		Woman woman=new Woman();
		func(man);
		
		System.out.println();
		func(woman);
	}

다익스트라 알고리즘 (Dijkstra Algorithm)

최단거리를 구하는 데에는 꽤 여러가지 알고리즘이 존재합니다. 그 중에서 가장 유명한 알고리즘, 다익스트라 알고리즘에 대해서 알아보도록 하겠습니다.

다익스트라 알고리즘은 무엇일까요?

그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 것이 이 알고리즘입니다. 

우선 아래와 같은 그래프가 있다고 가정해볼게요.

정점 0에서 모든 정점까지의 최단거리는 어떻게 될까요?

0번에서부터 5번 정점 중 임의의 i까지 최단 거리를 dist[i]라고 할때

가 됩니다.

이와 같이 어떤 시작점을 정해서 그 정점부터 다른 정점까지의 최단거리를 구하는 알고리즘이 바로 단일 시작점 알고리즘이고, 대표적인 알고리즘이 바로 다익스트라 알고리즘입니다.

BFS 최단거리 기반

이 알고리즘은 최단 거리를 구하는 것이기 때문에 BFS를 기반으로 움직이는데요. BFS는 자료구조에서 큐를 썼었죠? 따라서 다익스트라 알고리즘 역시 큐를 사용하여 구현할 수 있다는 사실을 알아두세요.

주의 사항은 위의 그래프가 나타내는 것처럼 음수간선이 있으면 다익스트라 알고리즘을 쓸 수가 없어요.

다익스트라 구현 (C++)

코드로 다익스트라 알고리즘을 살펴본 후 설명하도록 하겠습니다.

#include <vector>
#include <iostream>
#include <queue>

#define MAX_V 100
#define INF 99999999
using namespace std;


vector<pair<int, int> > adj[100];
vector<int> dijkstra(int start, int V) {
	vector<int> dist(V, INF);
	dist[start] = 0;
	priority_queue<pair<int, int> > q;
	q.push(make_pair(0, start));

	while (!q.empty()) {
		int cost = -q.top().first;
		int from = q.top().second;
		q.pop();

		if (dist[from] < cost) continue;

		for (int i = 0; i < adj[from].size(); i++) {
			int to = adj[from][i].first;
			int distFromTo = cost + adj[from][i].second;
			if (distFromTo < dist[to] ) {
				dist[to] = distFromTo;
				q.push(make_pair(-distFromTo, to));
			}
		}
	}
	return dist;
}

int main(int argc, char **argv)
{
	int E, V;
	printf("[input] vertex edge :");
	scanf("%d %d", &V, &E);

	
	for (int i = 0; i < E; i++) {
		printf("[input] from to cost :");
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		adj[from].push_back(make_pair(to, cost));
		adj[to].push_back(make_pair(from, cost));
	}

	printf("===dijkstra===\n");
	vector<int> dist = dijkstra(0, V);
	for (int i = 0; i < V; i++) {
		printf("from 0 to %d : %d\n", i, dist[i]);
	}
	return 0;
}

우선 입력을 받습니다. 위의 그래프 모양 그대로 입력을 받습니다. 위의 그래프를 조금 더 편하게 입력받으려면 아래의 input을 복사해서 붙여넣으세요.

이후 dijkstra가 어떻게 동작하는 지 그림을 보며 살펴보도록 합시다.

우선 우리가 반환한 dist의 벡터 사이즈를 V의 크기(정점의 개수)로 정하고 그 값을 아주 큰 값으로 설정합니다.

자기 자신과의 거리는 0이므로 dist[start]는 0으로 셋팅합니다.

여기서는 priority queue를 사용하는데요. 그 이유는 정점으로부터 가장 작은 값으로 연결되어 있는 정점을 꺼내는 것이 더 효율적이니까 그렇습니다.

또한 priority queue는 pair를 통해서 우선 순위를 정할때 첫번째 요소를 기준으로 가장 큰 값을 먼저 꺼내옵니다. 그래서 첫번째 요소를 거리, 그것도 -를 붙여서 넣어주면 값이 큰 간선으로 연결된 정점이 더 나중에 나오게 되는 것이죠.

그래서 꺼내올때 -를 붙여서 꺼내오고 -를 붙여서 집어 넣습니다.

이제 그림으로 더 쉽게 보도록 합시다.

우선 초기상태는 자기 자신의 정점을 우선순위 큐에 push하며 그 거리는 0이 됩니다. while루프를 돌기 전의 모습입니다. 

그 후 첫 while 루프를 돌면서 큐에 저장된 (0,0)을 가져옵니다. 0은 dist[0]보다 작지 않기 때문에 if문에 걸리지 않고 for루프를 돌게 됩니다. 주변에 가장 작은 값으로 연결된 정점은 2, 1, 3이지요. 그래서 그에 대응되는 거리 2, 3, 5와 함께 우선 순위 큐에 저장합니다. 

하지만 우선순위 큐는 큰 값이 먼저 선정되기 때문에 음수를 붙여서 -2,-3,-5로 바꾸어서 넣어줍니다.

** 아래 그림에서 잘못된 것이 있는데 우선순위 큐에 푸시되는 값은 (-2,2) (-3,1) (-5,3)인것으로 정정해주세요. 죄송해요.

우선순위 큐에서 2를 꺼내올때 이미 dist[2]는 2로, dist[2]보다 2가 더 작지 않으므로 if 조건문에 걸려 continue됩니다.

이 후 (-3, 1)을 꺼내옵니다. 정점 1에서 연결된 정점 중 가장 가까운 정점은 4입니다. 그렇기 때문에 dist[4]를 12로 수정하고 이 정보를 우선순위 큐에 저장합니다.

이제 (-5,3)을 꺼내올 차례이군요. dist[3]은 5이고, 큐에서 꺼내온 값 역시 5이므로 if문에 걸리지 않고 for루프를 돕니다. 이제 3에 연결되어 있는 정점은 4로 연결된 cost가 1인 간선입니다. 그래서 그전에 있던 dist[3]과 4로 연결된 간선의 cost 1을 더한 값(6)과 dist[4]와 연결된 값과 비교해보니 6이 더 작으므로 dist[4]=6으로 갱신하고 (-6,4)를 큐에 집어 넣습니다.

여기서 우선순위 큐를 사용하는 이유가 나옵니다. 만일 순서를 고려하지 않고 (-5, 3)이 큐에 맨 끝에 위치해있다면 이러한 갱신을 맨끝에 하게 되어 for루프를 돌게 되는 시간적인 낭비가 있게 되는 겁니다. 

그렇기 때문에 가장 비용이 낮은 것이 먼저 나오는 것이 유리하다는 것이죠.

다음 (-15,4)는 cost가 15이기 때문에 if조건에 걸려 continue됩니다. 

남은 (-6, 4)를 꺼내오게 되면 if조건문에 걸리지 않고 for루프를 돌아요. 4와 연결된 정점 5까지의 비용은 dist[4]와 3을 더한 9가 됩니다. 왜냐하면 dist[5]는 아주 큰 값이기 때문에 6이 더 작잖아요?

그 후 5와 연결된 간선의 정보를 큐에 저장합니다.

이제 마지막 (-9, 5)를 꺼내오는데, 이미 dist[5]=9이므로 if 조건에 걸려 continue됩니다. 이 후에는 큐가 비었으므로 while문을 탈출하게 되지요.

이제 모든 거리를 구했습니다.

코드에서는 0을 기준으로 구했는데 코드를 바꾸어서 1부터 시작해서 최단거리를 구해보세요. 그리고 비교해보세요.