이것 저것 &

1. TCP란?

전송제어 프로토콜로 OSI 7계층중에서 전송계층에 해당하는 프로토콜입니다.

데이터 전송을 할 때 신뢰성을 보장하는 프로토콜입니다.

즉, 네트워크상에서 발생할수 있는 데이타 누락, 패킷의 순서 뒤바뀜 등의 데이터 검사 및 교정과 관련된 기능이 있습니다.

인터넷 프로토콜 스위트(IP)의 핵심 프로토콜 중 하나로, IP와 함께 TCP/IP라는 명칭으로도 널리 불립니다. TCP는 근거리 통신망이나 인트라넷, 인터넷에 연결된 컴퓨터에서 실행되는 프로그램 간에 일련의 옥텟을 안정적으로, 순서대로, 에러없이 교환할 수 있게 합니다. TCP는 전송 계층에 위치합니다. 네트워크의 정보 전달을 통제하는 프로토콜이자 인터넷을 이루는 핵심 프로토콜의 하나로서 국제 인터넷 표준화 기구(IETF)의 RFC 793에 기술되어 있습니다.

이메일 전송, 파일 전송에 주로 사용됩니다. TCP의 안정성을 필요로 하지 않는 애플리케이션의 경우 일반적으로 TCP 대신 비접속형 사용자 데이터그램 프로토콜(User Datagram Protocol)을 사용합니다. 이것은 전달 확인 및 순차 보장 기능이 없는 대신 오버헤드가 작고 지연시간이 짧다는 장점이 있습니다.

이메일 전송, 파일 전송에는 TCP가 주로 사용되고 실시간 서비스와 같이 속도가 중요한 서비스에는 UDP를 많이 사용합니다. TCP의 안정성을 필요로 하지 않는 애플리케이션의 경우 일반적으로 TCP 대신 비접속형 사용자 데이터그램 프로토콜(User Datagram Protocol)을 사용합니다. 이것은 전달 확인 및 순차 보장 기능이 없는 대신 오버헤드가 작고 지연시간이 짧다는 장점이 있습니다.

아래는 TCP와 UDP 프로토콜의 차이점입니다.

아래는 TCP소켓의 동작 절차입니다.

socket()을 통해서 소켓을 생성합니다. 서버에서는 bind함수를 통해서 주소할당, listen함수를 통해서 연결요청 대기를 하게 됩니다. 클라이언트에서는 connect함수를 통해서 서버에 연결요청을 전달하게 되고 accpet를 통해서 연결요청을 허용하게 됩니다. 연결이 이루어진 후에 send/receive를 통해 소켓을 주고받게 됩니다. 

데이터 전송을 끝내고 close함수를 통해서 소켓을 종료하게 되는 구조입니다.

2. TCP 세그먼트 구조

TCP 세그먼트는 세그먼트 헤더와 데이터의 두 섹션으로 구성됩니다. TCP 헤더는 10개의 필수 필드 및 옵션 확장 필드(표 하단의 주황색 부분)들을 포함합니다.

헤더 뒤에는 데이터 섹션이 따라 옵니다. 그 내용은 애플리케이션의 페이로드 데이터입니다. 

Source port (16 비트): 송신 포트, 출발지 포트번호를 표시한다.

Destination port (16 비트): 수신 포트, 목적지 포트번호를 표시한다.

Sequence number (32 비트): SYN 플래그가 (1)로 설정된 경우, 이것은 초기 시퀀스 번호가 된다. 실제 데이터의 최초 바이트 값과 그에 상응하는 ACK 번호는 이 값에 1을 더한 값이 된다. SYN 플래그가 (0)으로 해제된 경우, 이것은 현재 세션의 이 세그먼트 데이터의 최초 바이트 값의 누적 시퀀스 번호이다.

Acknowledgment number (32 비트): ACK 플래그가 설정된 경우 이 필드의 값은 수신자가 예상하는 다음 시퀀스 번호이다. 이것은 모든 선행하는 바이트들(존재할 경우)에 대한 수신에 대한 확인응답이 된다. 한쪽이 보낸 최초의 ACK는 반대쪽의 초기 시퀀스 번호 자체에 대한 확인응답이 되며, 데이터에 대한 응답은 포함되지 않는다.

Data offset (4 비트): 32-bit 워드 단위로 나타낸 TCP 헤더 크기값이다. 헤더의 최소 크기는 5 워드이며 최대 크기는 15 워드이다. 따라서 최솟값은 20바이트, 최댓값은 60바이트가 되며, 헤더에 선택 값을을 위해 최대 40 바이트가 더 추가될 수 있다. 데이터 오프셋이라는 명칭은 이것이 실제 데이터 상에서의 TCP 세그먼트의 시작 위치의 오프셋이기 때문에 붙여졌다.

Reserved (3 비트): 미래에 사용하기 위해 남겨둔 예비 필드이며 0으로 채워져야 한다.

Flags (9 bits) (혹은 Control bits): 9개의 1-비트 플래그를 포함

NS (1 비트) – ECN-nonce 은폐 보호(RFC 3540에 의해 헤더에 추가).

CWR (1 비트) – 혼잡 윈도 축소(Congestion Window Reduced) 플래그는 송신측 호스트에 의해 설정되는 것으로, 호스트가 ECE 플래그가 포함된 TCP 세그먼트를 수신했으며 혼잡 제어 메커니즘에 의해 응답했음을 알리는 역할을 한다(RFC 3168에 의해 헤더에 추가).

ECE (1 비트) – ECN-Echo는 다음을 나타낸다.

SYN 플래그가 (1)로 설정된 경우, TCP 상대가 명시적 혼잡 통지(Explicit Congestion Notification, ECN)가 가능함을 의미한다.

SYN 플래그가 (0)으로 해제된 경우, IP 헤더 셋에 혼잡 경험(Congestion Experienced) 플래그가 설정된 패킷이 정상적인 전송 중에 수신되었다는 것을 의미한다(RFC 3168에 의해 헤더에 추가).

URG (1 비트) – Urgent pointer 필드의 값이 유효함을 나타낸다.

ACK (1 비트) – Acknowledgment 필드의 값이 유효함을 나타낸다. 클라이언트가 보낸 최초의 SYN 패킷 이후에 전송되는 모든 패킷은 이 플래그가 설정되어 있어야 한다.

PSH (1 비트) – 푸시 기능. 수신 애플리케이션에 버퍼링된 데이터를 푸시해 줄지 여부를 질의하는 역할을 한다.

RST (1 비트) – 커넥션 리셋

SYN (1 비트) – 동기화 시퀀스 번호. 양쪽이 보낸 최초의 패킷에만 이 플래그가 설정되어 있어야 한다. 다른 일부 플래그들의 의미가 이 플래그의 값에 따라 바뀌며, 일부 플래그들은 이 플래그가 설정되어 있을 때만 유효하고, 또 다른 일부 플래그들은 이 플래그가 해제되어 있을 때에만 유효하다.

FIN (1 비트) – 남은 송신측 데이터 없음

Window size (16 비트): 수신 윈도의 크기. 해당 세그먼트의 송신측이 현재 수신하고자 하는 윈도 크기(기본 단위는 바이트). acknowledgment 필드의 시퀀스 번호보다 큰 값이어야 한다.

Checksum (16 비트): 헤더 및 데이터의 에러 확인을 위해 사용되는 16 비트 체크섬 필드

Urgent pointer (16 비트): URG 플래그가 설정된 경우, 이 16 비트 필드는 시퀀스 번호로부터의 오프셋을 나타낸다. 이 오프셋이 마지막 긴급 데이터 바이트를 가리킨다.

Options (가변 0–320 비트, 32의 배수): 이 필드의 길이는 데이터 오프셋 필드에 의해 결정된다. 이 부분은 Option-Kind (1 바이트), Option-Length (1 바이트), Option-Data (가변) 이렇게 최대 3개의 필드로 구성될 수 있다. Option-Kind 필드는 옵션의 종류를 나타내며, 세 가지 필드 중 유일하게 필수값이다. 옵션의 종류에 따라 나머지 두 개의 필드가 설정될 수 있다. Option-Length 필드는 옵션의 전체 길이를 나타내며, Option-Data 필드는 적용 가능한 경우 해당 옵션의 값을 나타낸다. 예를 들어, Option-Kind 바이트 값이 0x01인 경우 이는 패딩의 용도로만 사용되는 옵션없음(No-Op) 옵션을 의미하며, 이 때에는 뒤따라 오는 Option-Length나 Option-Data 값이 존재하지 않는다. Option-Kind 바이트 값이 0인 경우 이는 옵션종료(End Of Options) 옵션을 의미하며, 전자와 마찬가지로 뒤따라 오는 추가 옵션 필드가 없다. Option-Kind 바이트 값이 0x02인 경우 이것은 최대 세그먼트 크기(Maximum Segment Size) 옵션을 의미하며, 그 뒤에는 MSS 필드의 길이값(0x04여야 함)이 따라오게 된다. 이 길이값은 Option-Kind와 Option-Length를 포함한 주어진 옵션 필드의 전체의 길이를 나타내는 것이다. 따라서 MSS 값은 일반적으로 2 바이트로 표현되며, 해당 필드의 길이는 4 바이트(kind와 length의 2바이트를 더한 값)가 된다. 실제 예를 들어 설명하면, 0x05B4라는 값을 갖는 MSS 옵션 필드는 (0x02 0x04 0x05B4)의 형태로 TCP 옵션 섹션에 나타날 것이다.

일부 옵션은 SYN 플래그가 설정되어 있을 때에만 송신된다. 이러한 옵션은 아래에 [SYN]으로 표시되어 있다. Option-Kind 및 기본 Option-Length는 (Option-Kind, Option-Length)으로 표시되었다.

0 (8 비트) – End of options list

1 (8 비트) – No operation (NOP, Padding) 이것은 속도 향상을 위해 옵션 필드를 32 비트 길이에 맞추기 위해 사용될 수 있다.

2,4,SS (32 비트) – Maximum segment size (최대 세그먼트 크기 참조) [SYN]

3,3,S (24 비트) – Window scale (윈도 조정 참조) [SYN][5]

4,2 (16 비트) – Selective Acknowledgement permitted. [SYN] (선택적 확인응답 참조)[6]

5,N,BBBB,EEEE,... (variable bits, N is either 10, 18, 26, or 34)- Selective ACKnowledgement (SACK)[7] 이 첫 2 바이트 뒤에는 선택적 확인응답을 받는 1-4개 블럭의 리스트가 따라오게 되며, 이들은 32 비트 시작/종료 포인터로 구분된다.

8,10,TTTT,EEEE (80 비트)- Timestamp and echo of previous timestamp (see TCP 타임스탬프 참조)[8]

14,3,S (24 비트) – TCP Alternate Checksum Request. [SYN][9]

15,N,... (가변 비트) – TCP Alternate Checksum Data.

(이외의 옵션들은 더이상 사용되지 않거나, 시험용이거나, 아직 표준화되지 않았거나, 또는 할당되지 않은 것들임)

Padding: TCP 헤더 패딩은 TCP 헤더의 종료 지점과 데이터의 시작 지점을 32 비트 단위 길이에 맞추기 위해 사용된다. 패딩의 값은 0이다.

3.TCP 프로토콜의 작동

 TCP 프로토콜의 작동은 크게 세 가지 흐름으로 구분한다.

1)     연결 생성 (Connection establishment)

2)     자료 전송 (Data transfer)

3)     연결 종료 (Connection termination)

연결할 때, 3 way handshaking을 진행한다.

신뢰성 있는 연결이 생성되어야 하며, 그 후 자료를 전송하고, 마지막으로 연결을 종료하면서 할당된 자원을 반납한다.

연결 생성

연결을 생성하기 위해, 3방향 핸드셰이크를 사용한다.

SYN: 클라이언트가 서버에게 SYN 메시지를 보낸다. 이 메시지에 포함된 시퀀스 번호는 클라이언트가 임의로 설정한 값 A.

SYN-ACK: 서버가 클라이언트에게 SYN-ACK 메시지로 응답한다. 이 메시지에 포함된 시퀀스 번호는 서버가 임의로 설정한 값 B, 응답 번호는 (A + 1).

ACK: 클라이언트가 서버에게 ACK 메시지를 보낸다. 이 메시지에 포함된 응답 번호는 (B + 1).

연결 종료

연결을 종료하기 위해, 4방향 핸드셰이크를 사용한다.              

1)     클라이언트가 연결을 종료하겠다는 FIN플래그를 전송한다.

2)     서버는 일단 확인메시지를 보내고 자신의 통신이 끝날때까지 기다리는데 이 상태가 TIME_WAIT상태다.

3)     서버가 통신이 끝났으면 연결이 종료되었다고 클라이언트에게 FIN플래그를 전송한다.

4)     클라이언트는 확인했다는 메시지를 보낸다.

4. TCP/IP 기반의 프로토콜

HTTP

HTTP(Hypertext Transfer Protocol)는 인터넷상에서 데이터를 주고 받기 위한 서버/클라이언트 모델을 따르는 프로토콜이다. HTTP는 어떤 종류의 데이터든지 전송할 수 있도록 설계돼 있다. HTTP로 보낼 수 있는 데이터는 HTML문서, 이미지, 동영상, 오디오, 텍스트 문서 등 여러종류가 있다.

FTP

서버와 클라이언트 사이의 파일 전송을 하기 위한 프로토콜이다.

SMTP

일반적으로 전자 메일 전송을위한 표준 프로토콜이다.

RTP

RTP(Real-time Transport Protocol)는 실시간 음성과 영상 및 데이터를 IP 네트워크로 전송하는 표준 프로토콜입니다.

RTP는 IETF RFC 3350 A Transport Protocol for Real-Time Applications 권고 안에서 정의하고 있습니다.

RTP는 RTCP(Real-time Control Protocol)를 이용하여서 데이터의 전달 상황을 감시 및 최소한의 제어 기능과 미디어 식별 등을 제공하고 있습니다.

4. TCP 패킷의 흐름제어, 오류제어, 혼잡제어

포스팅이 너무 길어져서 오류제어, 흐름제어, 혼잡제어는 포함하지 않았습니다.

아래 링크에 정리가 잘 되어 있으니 궁금하신 분들은 참고해주세요.

evan-moon.github.io/2019/11/22/tcp-flow-control-error-control/

출처: ko.wikipedia.org/wiki/%EC%A0%84%EC%86%A1_%EC%A0%9C%EC%96%B4_%ED%94%84%EB%A1%9C%ED%86%A0%EC%BD%9C

문제링크:www.acmicpc.net/problem/2606

기본적인 bfs, dfs 문제입니다.

vector를 통해서 양방향 그래프를 구현하고 완전탐색을 통해서 연결된 갯수를 파악하면 되는 문제입니다.

기본중에 기본문제입니다. 

이제 알고리즘을 입문하시는 분들이라면 그냥 코드자체를 외우듯이 이해하시면 될 것 같습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n = 0, m = 0, result = 0;
vector <int> vec[101];
bool visited[101] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		vec[t1].push_back(t2);
		vec[t2].push_back(t1);

	}

	queue <int> que;
	visited[1] = 1;
	que.push(1);

	while (!que.empty()) {
		int num = que.front();
		que.pop();

		for (int i = 0; i < vec[num].size(); i++) {
			int next = vec[num][i];
			if (visited[next] == 1) continue;
			que.push(next);
			visited[next] = 1;
			result++;
		}
	}

	cout << result << endl;
	return 0;
}

HLS(Http Live Streaming) 는 Apple(아이폰, 아이패드) 에서 사용하는 표준 HTTP 기반 스트리밍 프로토콜입니다. 프로토콜에서 스트리밍 데이터를 m3u8의 확장자를  가진 재생목록 파일과 잘게 쪼개놓은 다수의 ts 파일(동영상)을 HTTP를 통해 전송하는 방식을 사용합니다. 

• – m3u8 : m3u 파일인데, UTF-8 로 인코딩 되어 있다는 것
• – m3u : 멀티미디어 파일의 재생목록을 관리하는 파일
• – ts : MPEG-2 의 Transport Stream 포맷

apple의 수요가 증가하면서 자연스럽게 HLS의 수요도 증가하였고, 현재는 ios가 아니더라도 HLS를 많이 사용하고 있습니다. 

 이 프로토콜은 여러 미디어 플레이어, 웹 브라우저, 모바일 기기, 스트리밍 미디어 서버에서 지원되고 있습니다. 연간 비디오 산업 조사에 따르면 가장 대중적인 스트리밍 포맷으로 간주됩니다.

표준 HTTP 트랜잭션에 기반한 HTTP 라이브 스트리밍은 RTP 등 UDP 기반 프로토콜과 달리 표준 HTTP 트래픽을 통해 방화벽이나 프록시 서버를 경유할 수 있습니다. 또, 널리 이용되는 HTTP 기반 콘텐츠 전송 네트워크를 통해 콘텐츠를 전통적인 HTTP 서버로부터 제공받을 수 있습니다. 이 표준은 또한 표준 암호화 매커니즘과 HTTPS를 이용한 보안 키 배포를 사용하며 이 둘은 단순한 DRM 시스템을 제공하게 됩니다. 이 프로토콜의 후반 버전은 트릭 모드 빨리감기와 되감기, 자막 연동을 제공합니다.

출처:

ko.wikipedia.org/wiki/HTTP_%EB%9D%BC%EC%9D%B4%EB%B8%8C_%EC%8A%A4%ED%8A%B8%EB%A6%AC%EB%B0%8D

문제링크:www.acmicpc.net/problem/13549

대부분

• 순간 이동(0초 소요)은 걷는 이동(1초 소요)보다 더 빠르기때문에, 우선 순위가 높다. 

라는 조건을 생각해서 deque나 우선순위 큐를 사용해서 구현하셨더군요!

저는 일반 큐를 사용해서 구현했습니다. (수가 100,000까지 이기때문에 모든 방문노드를 들러도 된다고 인지했습니다. )

아래는 정답코드입니다.

천천히 확인해보세요.

#include <iostream>
#include <queue>
using namespace std;
int n = 0, k = 0;
int visited[100001] = { 0, };


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	queue <int> que;


	cin >> n >> k;
	que.push(n);
	visited[n] = 1;

	while (!que.empty()) {
		
		int v = que.front();
		que.pop();
		//cout << v << endl;
		for (int j = v; j <= 100000; j *= 2) { // 0초 후에 2*X의 위치로 이동
			if (j == 0) break;
			if (visited[j] == 0) {
				visited[j] = visited[v];
				que.push(j);
			}
		}
		if (visited[v + 1] == 0 && (v+1) <= 100000) {
			visited[v + 1] = visited[v] + 1;
			que.push(v + 1);
		}
		if (visited[v - 1] == 0 && (v-1) >= 0) {
			visited[v - 1] = visited[v] + 1;
			que.push(v - 1);
		}



	}

	cout << visited[k] - 1 << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/1967

문제풀이를 위해선 

1.가장 깊은 노드 중 가중치가 가장 큰 노드를 찾는다.

2. 찾은 노드를 기준 정점으로 잡고, 다시 한번 가장 가중치가 큰 노드를 찾는다.

2가지를 수행하면 된다.

왜 이렇게 되는지에 대한 증명은 구사과님 글을 참고하자.

koosaga.com/14

구현난이도는 쉽지만 아이디어 캐치가 어려운 문제였다.

이래서 개발자는 수학베이스가 있어야 하는것인가..

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n = 0;
bool visited[10001] = { 0, };
vector <pair<int, int>> arr[10001];

int result = 0;
int destination = 0;

void dfs(int cur, int len) {

	if (result < len) {
		result = len;
		destination = cur;
	}

	for (int i = 0; i < arr[cur].size(); i++) {
		if (visited[arr[cur][i].first] == 0) {
			visited[arr[cur][i].first] = 1;
			dfs(arr[cur][i].first, len + arr[cur][i].second);
		}
	}


}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int s, e, v;
		cin >> s >> e >> v;
		arr[s].push_back(make_pair(e, v));
		arr[e].push_back(make_pair(s, v));
	}

	visited[1] = 1;
	dfs(1, 0); //목적지 구하고
	cout << result << endl;
	
	memset(visited, 0, sizeof(visited));
	result = 0;
	
	visited[destination] = 1;
	dfs(destination, 0);

	cout << result << endl;
	

}

문제링크:www.acmicpc.net/problem/3980

dfs문제입니다. 

전형적인 dfs문제입니다. 백트래킹에 속하는 이유는 문제조건중에서

 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

라는 조건을 수행해야하기 때문입니다.

일반적인 dfs 방식을 사용해서 구현했습니다.

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t = 0, result = 0;
int arr[11][11] = { 0, };
bool visited[11];

void dfs(int cnt, int sum) {
	if (cnt == 11) {
		result = max(result, sum);
		return;
	}

	for (int i = 0; i < 11; i++) {
		if (arr[cnt][i] == 0)
			continue;
		if (visited[i] == 0) {
			visited[i] = 1;
			dfs(cnt + 1, sum + arr[cnt][i]);
			visited[i] = 0;
		}


	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> t;

	while (t--) {
		for (int i = 0; i < 11; i++)
			for (int j = 0; j < 11; j++)
				cin >> arr[i][j];
		memset(visited, 0, sizeof(visited));
		result = 0;
		dfs(0, 0);
		cout << result << "\n";
	}

}

문제링크:www.acmicpc.net/problem/16197

문제 조건에 따르며 구현했습니다.

두 동전의 좌표는 각각 c1y(coin 1 y좌표), c2x( coin 2 x 좌표)와 같은 형태로 나타냈습니다.

신경써야할 조건은 아래와 같습니다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
• 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1

조건에 맞추어 구현해주면 되는 dfs 겸 시뮬레이션 문제였습니다. 

아래는 정답코드입니다. 

1. 코인 두개 모두 범위안에 존재

2. 코인 둘 다 범위밖에 존재

3. 두개의 코인 중 하나만 밖으로 나감(결과 도출)

#include <iostream>
#include <string>
using namespace std;
int n, m;
int result = 2e9;
string arr[21]; //0base
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void dfs(int cnt, int c1y, int c1x, int c2y, int c2x) {
	
	if (cnt == 10)
		return;

	for (int i = 0; i < 4; i++) {
		int n1y = c1y + y_ar[i];
		int n1x = c1x + x_ar[i];
		int n2y = c2y + y_ar[i];
		int n2x = c2x + x_ar[i];
		if (n1y >= 0 && n1y < n && n2y >= 0 && n2y < n && n1x >= 0 && n1x < m &&  n2x >= 0 && n2x < m) {
			if (arr[n1y][n1x] == '#' && arr[n2y][n2x] == '#')
				continue;
			if (arr[n1y][n1x] == '#')
				n1y = c1y, n1x = c1x;
			if (arr[n2y][n2x] == '#')
				n2y = c1y, n2x = c1x;
			dfs(cnt + 1, n1y, n1x, n2y, n2x);
		}
		else if ((n1y < 0 || n1y >= n || n1x < 0 || n1x >= m) && (n2y < 0 || n2y >= n || n2x < 0 || n2x >= m)) {
			continue;
		}
		else {
			if (result > cnt + 1)
				result = cnt + 1;
			return;
		}
	}

}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int c1y, c1x, c2y, c2x;
	bool chk = false;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < m; j++)
			if (arr[i][j] == 'o'&& chk == false) {
				c1y = i, c1x = j;
				chk = true;
			}
			else if (arr[i][j] == 'o'&& chk == true) {
				c2y = i, c2x = j;
			}
	}
	dfs(0, c1y, c1x, c2y, c2x);
	if (result == 2e9)
		cout << -1 << endl;
	else
		cout << result << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/2239

일반적인 스도쿠문제와 동일합니다.

 다만,  "제일 작은 경우를 출력한다." 라는 조건이 추가됐습니다.

아래 링크와 같은 방법으로 해결해도 됩니다. 

gusdnr69.tistory.com/142

저는 직관적인 방법으로 결과를 도출했습니다.

아래는 정답 코드 입니다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int arr[9][9] = { 0, };
bool fin = false;
vector <pair <int, int>> zero_vec;

void dfs(int cnt) {
	if (cnt == zero_vec.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << arr[i][j];
			cout << endl;
		}
		fin = true;
		return;
	}
	if (fin == true)
		return;

	for(int i=cnt;i<zero_vec.size();i++){}
	int y = zero_vec[cnt].first;
	int x = zero_vec[cnt].second;

	bool temp[10] = { 0, };
	for (int i = 0; i < 9; i++) {
		temp[arr[y][i]] = 1;
		temp[arr[i][x]] = 1;
	}
	for (int i = y / 3 * 3; i < y / 3 * 3 + 3; i++)
		for (int j = x / 3 * 3; j < x / 3 * 3 + 3; j++)
			temp[arr[i][j]] = 1;

	for (int i = 1; i <= 9; i++)
		if (temp[i] == 0) {
			arr[y][x] = i;
			dfs(cnt + 1);
			arr[y][x] = 0;
		}


}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	for (int i = 0; i < 9; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < 9; j++) {
			arr[i][j] = temp[j] - '0';
			if (arr[i][j] == 0)
				zero_vec.push_back(make_pair(i, j));
		}
	}
	dfs(0);

	return 0;
}