Diademata

1. 가십 프로토콜이란?

가십 프로토콜은 분산 시스템에서 노드들이 정보를 교환하며 동기화하는 방식입니다. 이름 그대로, 소문(gossip)이 퍼지듯 정보가 네트워크 전체로 확산됩니다.

가십 프로토콜의 주요 특징

• 랜덤성: 정보가 무작위로 선택된 노드들에게 전파됩니다.
• 확장성: 네트워크의 크기가 커져도 효율적으로 작동합니다.
• 내결함성: 일부 노드가 고장 나더라도 전체 정보 전파에 문제가 없습니다.

2. 가십 프로토콜의 동작 방식

기본 개념

• 정보의 전파:
  • 새로운 정보를 가진 노드가 무작위로 선택된 다른 노드에게 정보를 전달합니다.
  • 선택된 노드들은 다시 새로운 노드를 선택해 정보를 전파합니다.
  • 이 과정이 반복되면서 네트워크 전체로 정보가 확산됩니다.

3. 전파 수(Fanout)

전파 수란?

• 전파 수는 한 번에 정보를 전파할 노드의 수를 의미합니다.
• 일반적으로 2개 이상의 노드로 정보를 전파하는 방식이 사용됩니다.

전파 수가 1인 경우의 위험성

1. 느린 확산 속도
   • 단일 노드로만 정보가 전달되므로, 네트워크 전체에 정보가 퍼지는 데 시간이 오래 걸립니다.
   • 예: 100개의 노드가 있을 경우, 모든 노드가 정보를 받으려면 최소 100번의 전파 라운드가 필요합니다.
2. 단일 장애 지점(Single Point of Failure)
   • 정보를 전달받은 노드가 장애를 겪으면 정보가 더 이상 전파되지 않을 가능성이 큽니다.
3. 네트워크 안정성 저하
   • 전파 경로가 단일 노드에 의존하므로, 일부 노드가 정보를 누락하거나 분리될 경우 동기화가 지연됩니다.

전파 수가 2개 이상일 경우의 장점

1. 빠른 확산 속도
   • 정보가 병렬로 여러 노드에 전파되므로, 네트워크 전체로 기하급수적으로 빠르게 확산됩니다.
   • 예: 전파 수가 2이고 네트워크에 100개의 노드가 있다면, log⁡2(100)≈7\log_2(100) \approx 7log2​(100)≈7 라운드 안에 모든 노드가 정보를 받을 가능성이 매우 높습니다.
2. 내결함성 강화
   • 하나의 노드가 실패하더라도 정보는 다른 경로를 통해 계속 전달될 수 있습니다.
3. Eclipse 공격 방지
   • 정보를 다양한 경로로 전파함으로써, 악의적인 노드가 네트워크를 점령하려는 시도를 방어할 수 있습니다.
4. 네트워크 안정성 보장
   • 다수의 노드가 정보를 동시에 수신하므로, 일부 노드에서 정보가 누락되더라도 빠르게 복구됩니다.

4. 가십 프로토콜의 장점

1. 확장성
   • 네트워크 크기가 커져도 정보 전파가 효율적으로 이루어집니다.
   • 노드 추가나 삭제가 발생해도 시스템 동작에 큰 영향을 주지 않습니다.
2. 빠른 정보 확산
   • 병렬로 다수의 노드에 정보를 전달하므로 매우 빠르게 정보가 퍼집니다.
3. 내결함성
   • 일부 노드가 장애를 겪더라도 정보 전파가 계속 진행됩니다.
4. 구현의 단순성
   • 구현이 비교적 간단하며, 네트워크 대역폭과 시스템 자원을 효율적으로 사용합니다.

5. 가십 프로토콜의 한계와 보완점

한계

1. 지연(Latency)
   • 랜덤 전파로 인해 일부 노드가 정보를 늦게 받을 가능성이 있습니다.
2. 중복 메시지 전송
   • 동일한 정보가 여러 노드를 통해 반복적으로 전달되어 네트워크 리소스가 낭비될 수 있습니다.

6. 결론

가십 프로토콜은 분산 시스템에서 효율적이고 신뢰성 높은 정보 전파를 가능하게 하는 핵심 메커니즘입니다. 단순하지만 강력한 설계 덕분에 대규모 네트워크에서도 널리 사용됩니다.

전파 수 설정의 중요성

• 전파 수가 1인 경우에도 작동하지만, 정보 손실 위험과 확산 속도 저하의 문제가 있습니다.
• 따라서 2개 이상의 전파 수를 사용하면 정보가 빠르고 신뢰성 있게 네트워크 전체로 확산됩니다.

1. Task와 async/await

• async/await: C#의 async와 await 키워드는 비동기 메서드를 쉽게 작성할 수 있게 해준다. async 키워드를 메서드에 붙이면 컴파일러는 해당 메서드를 상태 머신(state machine)코드로 변환한다. await는 비동기 작업이 완료될 때까지 메서드의 실행을 일시 중단(suspend)하고, 작업이 완료되면 메서드를 재개(resume)한다

2. IAsyncStateMachine의 역할

• 상태 머신(State Machine): async 키워드가 붙은 메서드는 내부적으로 컴파일러에 의해 상태 머신 클래스 코드로 변환된다. 이 상태 머신 클래스는 IAsyncStateMachine 인터페이스를 구현한다. 상태 머신는 비동기 작업의 흐름을 관리하며, await 키워드에 의해 메서드가 일시 중단되고 다시 실행되는 과정을 처리한다
• MoveNext 메서드: 상태 머신의 핵심 메서드는 MoveNext이다. 이 메서드는 메서드의 실행 상태를 진행시키는 역할을 하며, 비동기 작업이 완료될 때마다 호출된다. await 키워드에 의해 비동기 작업이 일시 중단된 이후, 해당 작업이 완료되면 MoveNext가 호출되어 다음 상태로 넘어가고, 메서드가 재개된다.

아래의 코드에서 ExampleAsync는 상태 머신 클래스로 변환된다.

using System;
using System.Threading.Tasks;

public class Program
{
    public static async Task<int> ExampleAsync()
    {
        // 1초 동안 비동기 대기
        await Task.Delay(1000);
        
        Console.WriteLine("Tset");

        return 42; // 결과 반환
    }

    private static void Main()
    {
        Console.WriteLine("Main : block 1");

        // 비동기 메서드 호출, Task<int> 반환
        var task = ExampleAsync();

        Console.WriteLine("Main : block 2");

        // 결과가 반환될 때까지 대기 (동기적 대기)
        task.Wait();

        Console.WriteLine($"Result: {task.Result}");

        // 프로그램이 종료되지 않도록 대기
        Console.ReadLine();
    }
}

디컴파일된 코드는 일반적으로 다음과 같은 형태로 보인다. 아래는 ILSpy를 통해 디컴파일된 코드의 예시

// TaskStateMachine, Version=1.0.0.0, Culture=neutral, PublicKeyToken=null
// Program.<ExampleAsync>d__0
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Threading.Tasks;

[CompilerGenerated]
private sealed class <ExampleAsync>d__0 : IAsyncStateMachine
{
	public int <>1__state;

	public AsyncTaskMethodBuilder<int> <>t__builder;

	private TaskAwaiter <>u__1;

	private void MoveNext()
	{
		int num = <>1__state;
		int result;
		try
		{
			TaskAwaiter awaiter;
			if (num != 0)
			{
				awaiter = Task.Delay(1000).GetAwaiter();
				if (!awaiter.IsCompleted)
				{
					num = (<>1__state = 0);
					<>u__1 = awaiter;
					<ExampleAsync>d__0 stateMachine = this;
					<>t__builder.AwaitUnsafeOnCompleted(ref awaiter, ref stateMachine);
					return;
				}
			}
			else
			{
				awaiter = <>u__1;
				<>u__1 = default(TaskAwaiter);
				num = (<>1__state = -1);
			}
			awaiter.GetResult();
			Console.WriteLine("Tset");
			result = 42;
		}
		catch (Exception exception)
		{
			<>1__state = -2;
			<>t__builder.SetException(exception);
			return;
		}
		<>1__state = -2;
		<>t__builder.SetResult(result);
	}

	void IAsyncStateMachine.MoveNext()
	{
		//ILSpy generated this explicit interface implementation from .override directive in MoveNext
		this.MoveNext();
	}

	[DebuggerHidden]
	private void SetStateMachine(IAsyncStateMachine stateMachine)
	{
	}

	void IAsyncStateMachine.SetStateMachine(IAsyncStateMachine stateMachine)
	{
		//ILSpy generated this explicit interface implementation from .override directive in SetStateMachine
		this.SetStateMachine(stateMachine);
	}
}

Task에서 예외가 터질 때 콜 스택에 MoveNext가 찍혀서 처음엔 IEnumerator의 MoveNext인 줄 알았다. 면접 덕분에 조금 더 찾아보게 되고 IAsyncStateMachine의 MoveNext라는 걸 알게 되었다. 이렇게 또 하나 배워간다.

• Task 생성 및 시작:
  • Task 객체가 생성되면, 아직 실행되지 않은 상태. 예를 들어, Task.Run() 또는 Task.Factory.StartNew() 메서드를 호출하면 Task가 실행 준비 상태가 된다.
  • Task는 작업 내용을 정의한 delegate(예: Action 또는 Func)를 인자로 받는다.
• 작업 대기열에 추가 (큐잉):
  • Task가 시작되면, 작업은 스레드 풀의 작업 대기열에 큐잉된다.. 이 작업 대기열은 스레드 풀에서 관리하며, 실행 대기 중인 작업들을 순차적으로 처리한다.
  • 작업이 큐잉된 후, 스레드 풀은 사용 가능한 스레드를 선택하여 해당 작업을 할당한다.
• 스레드 풀에서 스레드 선택:
  • 스레드 풀은 관리되는 스레드 풀 안에서 현재 유휴 상태인 스레드를 사용하거나, 필요에 따라 새로운 스레드를 생성하여 작업을 처리한다.
  • 스레드 풀의 스레드 수는 최적의 성능을 위해 동적으로 관리된다.
• 작업 실행:
  • 할당된 스레드가 작업을 실행하기 시작한다.
  • 작업이 비동기 작업을 포함하는 경우, await 키워드나 비동기 메서드를 통해 스레드가 다른 작업을 할 수 있도록 반환될 수 있다.
• 작업 완료:
  • 작업이 완료되면, Task는 완료 상태로 전환된다. 이때 Task 객체는 성공적으로 완료되었는지, 예외가 발생했는지, 또는 작업이 취소되었는지에 대한 상태를 가진다.
  • 완료된 Task는 관련된 ContinueWith나 await를 사용하여 후속 작업(콜백)으로 이어질 수 있다.
• 결과 반환 (옵션):
  • Task<TResult>를 사용하는 경우, 작업이 완료되면 결과 값을 반환할 수 있다.
  • 작업이 완료된 후, 스레드 풀은 해당 스레드를 반환하여 다른 작업을 처리할 수 있도록 준비한다.

구조체와 클래스는 C#에서 각각 값 타입과 참조 타입으로 다르게 동작한다.

구조체와 클래스의 메모리 기본적인 메모리 할당은 구조체는 스택, 클래스는 항상 힙에 할당이 된다.

아래의 코드를 보면 MyStruct는 MyClass를 멤버 변수로 가지고 있다.

구조체의 ReferenceType는 스택에 올라갈까? 그렇지 않다.

classInstance는 힙에 할당되고 structInstance는 스택에 할당된다. 구조체의 ReferenceType는 힙에 할당되어 있는 classInstance를 참조하게 된다.

public class MyClass
{
    public int Value { get; set; }

    public MyClass(int value)
    {
        Value = value;
    }
}

public struct MyStruct
{
    public MyClass ReferenceType { get; set; }
    public int Number { get; set; }

    public MyStruct(int number, MyClass referenceType)
    {
        Number = number;
        ReferenceType = referenceType;
    }
}

void Main()
{
    MyClass classInstance = new MyClass(100);
    MyStruct structInstance = new MyStruct(10, classInstance);

    Console.WriteLine($"Number: {structInstance.Number}, Value: {structInstance.ReferenceType.Value}");

    structInstance.ReferenceType.Value = 200;
    Console.WriteLine($"Updated Value: {classInstance.Value}"); // 200
}

구조체는 스택에 생성, class는 힙에 생성 라는 생각에 매몰되어 오해할 수 있는데 클래스의 맴버 변수이기 때문에 classInstance의 힙 메모리 내에 직접 할당이 된다.

public struct MyStruct
{
    public int X;
    public int Y;
}

public class MyClass
{
    public MyStruct Position;
}

void Main()
{
    MyClass classInstance = new MyClass();
    classInstance.Position = new MyStruct { X = 10, Y = 20 };

    Console.WriteLine($"X: {classInstance.Position.X}, Y: {classInstance.Position.Y}");
}

최종 정리를 하자면

• 구조체는 스택에, 클래스는 힙에 할당된다는 일반적인 규칙이 맞지만, 구조체가 클래스의 멤버로 포함될 때는 예외가 있다.
• 구조체가 클래스를 멤버로 가지는 경우, 구조체는 스택에 할당되더라도, 해당 구조체의 참조 타입 멤버는 힙에 할당된 클래스를 참조한다.
• 클래스가 구조체를 멤버로 가지는 경우, 구조체는 클래스와 함께 힙에 할당된다.

Dictionary와 HashTable은 모두 Key-Value 저장하는 자료구조이다.

몇 가지 차이점이 존재한다.

차이점

Dictionary :

- 제너릭 타입을 사용한다. 키와 값을 명시적으로 지정해야한다.

Hashtable

- object 타입으로 키와 값을 저장한다.

- 타입의 안정성을 제공하지 않음으로 런타임 에러가 발생할 수 있다.

- 박싱, 언박싱이 발생 할 수 있다.

HashTable의 문제점을 개선한 것이 Dictionary 자료 구조이다.

Dictionary 내부 자료 구조는 HashTable을 사용한다.

private int FindEntry(TKey key) 
{
    if( key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets != null) {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
        }
    }
    return -1;
}

그리고 SortedDictionary 은 TreeSet<T> 이라는 자료구조를 사용하고 있는데 TreeSet은 SortedSet<T>을 상속 받아서 사용된다.

    [Serializable]
    internal class TreeSet<T> : SortedSet<T> {
 
        public TreeSet()
            : base() { }
 
        public TreeSet(IComparer<T> comparer) : base(comparer) { }
 
        public TreeSet(ICollection<T> collection) : base(collection) { }
 
        public TreeSet(ICollection<T> collection, IComparer<T> comparer) : base(collection, comparer) { }
 
        public TreeSet(SerializationInfo siInfo, StreamingContext context) : base(siInfo, context) { }
 
        internal override bool AddIfNotPresent(T item) {
            bool ret = base.AddIfNotPresent(item);
            if (!ret) {                
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);                
            }
            return ret;
        }
 
    }

SortedSet<T> 의 내부 알고리즘을 보게 되면 Red-Black Tree를 사용하고 있다.

//
// A binary search tree is a red-black tree if it satisfies the following red-black properties:
// 1. Every node is either red or black
// 2. Every leaf (nil node) is black
// 3. If a node is red, then both its children are black
// 4. Every simple path from a node to a descendant leaf contains the same number of black nodes
// 
// The basic idea of red-black tree is to represent 2-3-4 trees as standard BSTs but to add one extra bit of information  
// per node to encode 3-nodes and 4-nodes. 
// 4-nodes will be represented as:          B
//                                                              R            R
// 3 -node will be represented as:           B             or         B     
//                                                              R          B               B       R
// 
// For a detailed description of the algorithm, take a look at "Algorithms" by Robert Sedgewick.
//

https://doc.akka.io/docs/akka/current/typed/cluster-membership.html

https://getakka.net/articles/clustering/cluster-overview.html

Akka 클러스터 형성 과정은 클러스터가 올바르게 초기화되고 유지되도록 보장하기 위해 여러 주요 구성 요소와 단계를 포함한다. 다음은 클러스터가 형성되는 방법, 노드의 다양한 유형의 역할, 그리고 노드 상태 및 클러스터 무결성 관리 메커니즘에 대한 설명이다.

1. 시드 노드와 비시드 노드

• 시드 노드(Seed Nodes): 잘 알려진 IP 주소/포트 조합을 가진 노드로, 클러스터 구성에서 미리 정의된다. 다른 노드가 클러스터에 가입할 때 초기 연락 점 역할을 한다.
• 비시드 노드(Non-seed Nodes): 초기에는 주소가 알려지지 않은 노드로, 클러스터를 형성하기 위해 시드 노드에 연락해야 한다.

2. 초기 클러스터 형성

• 클러스터는 시드 노드가 서로를 알고 있는 상태에서 시작한다. 예를 들어, A와 B 두 시드 노드가 있으면, 이 노드들은 서로의 존재를 인식하고 설정된다.
• 비시드 노드(C, D, E와 같은)는 적어도 하나의 시드 노드에 연락할 수 있도록 구성된다.
• 구성에서 첫 번째로 나열된 시드 노드는 반드시 작동 중이어야 한다.. 그렇지 않으면 클러스터가 형성되지 않는다. 이는 초기 시작 시 분산 브레인(scenarios) 같은 문제를 방지하기 위한 것이다.

3. 연결 설정

• 비시드 노드는 지정된 시드 노드에 연결을 시도한다. 예를 들어, C와 D 노드는 A에, E 노드는 B에 연결하도록 설정될 수 있다.
• 모든 노드는 클러스터 형성 과정을 시작하기 위해 시드 노드에 연결을 시도한다.

4. 리더 선출

• 노드가 클러스터에 합류함에 따라 리더가 선출된다.. 리더는 일반적으로 시드 노드 중 하나이며, 클러스터 상태를 관리하는 책임이 있다.
• 리더는 직접 통신할 수 있는 노드부터 시작하여 알고 있는 노드들을 활성 상태로 표시하기 시작한다.

5. 가십 프로토콜

• 클러스터 멤버십에 대한 가십(gossip) 정보가 모든 노드에 퍼지기 시작한다. 이 정보에는 어떤 노드들이 활성화되어 있고 그들의 연결 상태가 포함된다.
• 노드들은 지속적으로 통신을 하며, 각 노드가 다른 모든 노드와 연결된 메시 네트워크를 형성한다.

6. 클러스터 무결성 및 관리

• 클러스터가 운영되는 동안, 노드들은 서로에게 지속적으로 하트비트를 보내 가용성을 확인한다. 하트비트를 충분히 보내지 못하면 노드는 동료들에 의해 접근 불가능하다고 표시된다.
• 리더는 접근 불가능한 노드가 다시 접근 가능해지거나 공식적으로 클러스터에서 제거될 때까지 클러스터 결정을 중단한다. 클러스터의 상태가 일관되지 않은 경우 리더는 자신의 업무를 수행할 수 없다고 표시한다.

7. 노드 고장 및 퇴출 처리

• 노드가 접근 불가능해지면 설정된 타임아웃(auto-down-unreachable-after)을 사용하여 노드를 영구적으로 제거(다운)하기로 결정할 수 있다.
• 노드는 클러스터에서 우아하게 퇴출될 수도 있으며, 이는 노드가 접근 불가능하게 표시되는 것을 방지한다.

8. 조정된 종료

• 노드가 클러스터에서 우아하게 종료할 수 있도록 조정된 종료 프로세스를 제공한다.

daemon.json 등록

sudo vi /etc/docker/daemon.json

호스트 입력

{
 "hosts": ["unix:///var/run/docker.sock", "tcp://0.0.0.0:2375"]
}

서비스를 확인한다.

sudo vi /lib/systemd/system/docker.service

서비스에 -H 플래그가 있다면 Daemon.json의 호스트와 충돌이 발생할 수 있다.

ExecStart=/usr/bin/dockerd -H fd:// --containerd=/run/containerd/containerd.sock

아래와 같이 제거를 한다.

ExecStart=/usr/bin/dockerd --containerd=/run/containerd/containerd.sock

git filter-branch -f --env-filter '

UPDATE_NAME="username"
UPDATE_EMAIL="user@mailadress"

if [ "$GIT_COMMITTER_EMAIL" = "old@mail.com" ]
then
    export GIT_AUTHOR_NAME="$UPDATE_NAME"
    export GIT_COMMITTER_NAME="$UPDATE_NAME"
    export GIT_COMMITTER_EMAIL="$UPDATE_EMAIL"
fi
if [ "$GIT_AUTHOR_EMAIL" = "old@mail.com" ]
then
    export GIT_AUTHOR_NAME="$UPDATE_NAME"
    export GIT_COMMITTER_NAME="$UPDATE_NAME"
    export GIT_COMMITTER_EMAIL="$UPDATE_EMAIL"
fi
if [ "$GIT_COMMITTER_NAME" = "oldusername" ]
then
    export GIT_AUTHOR_NAME="$UPDATE_NAME"
    export GIT_COMMITTER_NAME="$UPDATE_NAME"
    export GIT_COMMITTER_EMAIL="$UPDATE_EMAIL"
fi
if [ "$GIT_AUTHOR_NAME" = "oldusername" ]
then
    export GIT_AUTHOR_NAME="$UPDATE_NAME"
    export GIT_COMMITTER_NAME="$UPDATE_NAME"
    export GIT_COMMITTER_EMAIL="$UPDATE_EMAIL"
fi

' --tag-name-filter cat -- --branches --tags

rebase를 통해서 하는 것보다 훨씬 더 수월하게 잘못 커밋된 계정을 변경할 수 있다.

git push -f

쌓인 커밋들을 다시 푸시하면 된다.

메모리 매핑 파일(Memory-Mapped File)은 파일이나 장치의 내용을 메모리 주소 공간에 매핑하는 기술이다. 이 방법을 사용하면 파일이나 장치의 데이터에 대한 접근을 마치 메모리에 직접 있는 데이터에 접근하는 것처럼 수행할 수 있다. 이는 데이터의 읽기와 쓰기 속도를 향상시킬 수 있으며, 대용량 파일 처리에 특히 유용하다.

메모리 매핑 파일을 이용한 프로세스 간 공유는 고성능의 IPC 메커니즘을 제공하며, 파일 입출력보다 훨씬 빠른 데이터 접근 속도를 가능하게 한다. 그러나 공유 데이터에 대한 동시 접근을 관리하는 것이 중요하며, 적절한 동기화 방법을 선택하여 데이터의 일관성과 무결성을 보장해야 한다.

작동 원리

1. 매핑 생성: 운영 체제는 파일의 내용을 프로세스의 가상 메모리 주소 공간에 매핑한다. 이 과정에서 실제 물리 메모리의 할당은 필요한 부분이 실제로 접근될 때까지 지연된다.
2. 데이터 접근: 프로그램은 메모리 주소를 통해 파일 데이터에 접근할 수 있게 된다. 이 때, 파일 내용은 메모리에 있는 것처럼 읽기, 쓰기, 수정이 가능하다.
3. 변경 사항 반영: 메모리에 있는 데이터에 대한 변경 사항은 시스템에 의해 자동으로 파일에 반영된다. 이는 주기적으로 또는 메모리 매핑이 해제될 때 수행될 수 있다.

장점

• 성능 향상: 메모리 매핑을 사용하면 파일 입출력(I/O) 연산이 메모리 접근 연산으로 대체된다. 이는 입출력 연산의 오버헤드를 줄이고 성능을 향상시킨다.
• 간편한 데이터 접근: 배열이나 포인터를 사용해 직접 메모리에 접근하는 것처럼 파일 데이터에 접근할 수 있어, 복잡한 파일 입출력 코드를 단순화할 수 있다.
• 대용량 파일 처리: 메모리 매핑은 파일 전체를 메모리에 로드하지 않고 필요한 부분만 로드하기 때문에, 사용 가능한 물리 메모리보다 큰 파일도 효율적으로 처리할 수 있다.

https://www.acmicpc.net/problem/14503

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 N X M 크기의 직사각형으로 나타낼 수 있으며, 1 X 1 크기의 정사각형 칸으로 나누어져 있다.
각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0) 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 즉, 좌표 (r,c) 는 북쪽에서 (r + 1)번째에 있는 줄의 서쪽에서 (c + 1)번째 칸을 가리킨다.

처음에 빈 칸은 전부 청소되지 않은 상태이다. 로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90도 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

#include <iostream>
#include<memory.h>

int N, M;
int r[50][50];
int v[50][50];

//d = 0 북
//d = 1 동
//d = 2 남
//d = 3 서

int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int count = 0;
bool DFS(int x, int y, int d)
{
    //std::cout << y << "," << x  << std::endl;
    if (v[y][x] == 0)
    {
        v[y][x] = 1;
        count++;
    }
    for (int i = 0; i < 4; ++i)
    {
        int nd = (d + 3 - i) % 4;
        int nx = x + dx[nd];
        int ny = y + dy[nd];

        if (r[ny][nx] == 0 && v[ny][nx] == 0)
        {
            v[ny][nx] = 1;
            count++;
            if (DFS(nx, ny, nd) == false)
                return false;
        }
    }
    int bd = (d + 2) % 4;
    int bx = x + dx[bd];
    int by = y + dy[bd];
    if (r[by][bx] == 0)
    {
        if (DFS(bx, by, d) == false)
            return false;
    }
    else if(r[by][bx] == 1)
        return false;
    return true;
}
int main()
{
    std::ios::ios_base::sync_with_stdio(false);
    memset(r, -1, sizeof(r));

    std::cin >> N >> M;

    int x, y, d;

    std::cin >> y >> x >> d;

    for (int i = 0; i < N; ++i)
    {
        for (int ii = 0; ii < M; ++ii)
        {
            std::cin>> r[i][ii];
        }
    }
    DFS(x, y, d);
    std::cout << count;
}

이동하는 모습을 디버깅해보면서 풀면 된다.