250718

lililllilillll·2025년 7월 18일

개발 일지

목록 보기

236/350

✅ 한 것들

백준
모두의 네트워크 기초

⚔️ 백준

3197 백조의 호수

시간 초과 풀이

#include"3197.h"
#define INF 0x3f3f3f3f
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef pair<int, int> pii;

// 실수 1. using namespace std 뒤에 typedef 선언해야 되는거 몰랐음
// 실수 2. vector 제대로 초기화 안 하고 새로 선언으로 떼우려고 함.
// 실수 3. 물이랑 겹치는 것만 넣어야 되는데, 모든 얼음을 큐에 넣어버렸음.
// 실수 4. 오리 둘 다 bfs 때려야 얼음이 골고루 녹는데 한 오리만 bfs 때림
// 실수 5. 오리 둘 다 bfs 때려도 얼음이 감싼 얼음은 안 녹음. 따로 bfs 해야됨.

// 이전 체크에서 얼음이었던 곳에서부터 bfs 다시 시작하도록 하여 최적화했는데 시간초과

bool IsValidXY(int& R, int& C, vector<string>& lake, int& newx, int& newy)
{
	if (0 <= newx && newx < R && 0 <= newy && newy < C) return true;
	else return false;
}

void B3197::Solution()
{
	fastio;

	// 얼음 녹인 뒤에 오리 한 쪽에서부터 갈 수 있는지 체크.
	// 근데 이전 체크에서 얼음이었던 곳에서부터 bfs 다시 시작함.
	int R, C;
	string s;
	cin >> R >> C;
	vector<string> lake(R);
	pii duck;
	queue<pii> iceq;

	vector<int> dx = { 1,-1,0,0 };
	vector<int> dy = { 0,0,1,-1 };

	vector<vector<bool>> visited(R, vector<bool>(C));
	vector<vector<bool>> willmelt(R, vector<bool>(C));
	for (int i = 0; i < R; i++) {
		cin >> lake[i];
	}

	// 녹일 얼음을 확인
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (lake[i][j] == 'L') { duck = { i,j }; }
			else if (lake[i][j] == 'X') {
				for (int k = 0; k < 4; k++) {
					int newx = i + dx[k];
					int newy = j + dy[k];
					if (IsValidXY(R, C, lake, newx, newy)
						&& lake[newx][newy] == '.') {
						willmelt[i][j] = true;
						iceq.push({ i,j });
						break;
					}
				}
			}
		}
	}

	bool done = false;
	int day = 0;
	queue<pii> duckq;
	duckq.push(duck);
	visited[duck.first][duck.second] = true;
	while (true)
	{
		// 오리가 방문하지 않은 물을 전부 탐색
		while (!duckq.empty()) {
			pii d = duckq.front(); duckq.pop();
			for (int i = 0; i < 4; i++) {
				int newx = d.first + dx[i];
				int newy = d.second + dy[i];
				if (IsValidXY(R, C, lake, newx, newy)
					&& !visited[newx][newy])
				{
					if (lake[newx][newy] == '.') {
						visited[newx][newy] = true;
						duckq.push({ newx,newy });
					}
					else if (lake[newx][newy] == 'L') {
						done = true;
						break;
					}
				}
			}
			if (done) break;
		}
		if (done) break;

		// 얼음을 녹일 때 상하좌우 확인하고 다음 녹일 얼음 확인
		int iceqlen = iceq.size();
		while(iceqlen--) {
			pii ice = iceq.front(); iceq.pop();
			int icex = ice.first, icey = ice.second;
			lake[icex][icey] = '.';
			bool newduck = false;
			for (int i = 0; i < 4; i++) {
				int newx = icex + dx[i], newy = icey + dy[i];
				if (IsValidXY(R, C, lake, newx, newy))
				{
					// 상하좌우에 오리가 방문한 물이 있다면 오리 큐에 추가
					if (visited[newx][newy] && lake[newx][newy] == '.') {
						newduck = true;
					}
					// 상하좌우에 아직 녹을 예정도 아닌 얼음이 있다면 녹일 예약
					else if (!willmelt[newx][newy] && lake[newx][newy] == 'X') {
						willmelt[newx][newy] = true;
						iceq.push({ newx,newy });
					}
				}
			}
			if (newduck) { 
				visited[icex][icey] = true;
				duckq.push(ice); 
			}
		}

		// 얼음을 녹일 때 중복 계산을 하지 않도록 visited를 체크하면
		// 다음 duck bfs 때 visited 하지 않은 얼음을 nextdq에 담아놓을 수 없다
		// willmelt를 선언한 후 얼음 녹는 bfs는 따로 체크한다면
		// 시간 초과 발생했던 풀이가 됨
		// 문제가 발생한 부분 : nextdq? > 하지만 그래봤자 계산 증가 최대 x3

		// 얼음을 녹일 때 상하좌우에 visited한 물이 있고
		// 그 얼음이었던 물을 다음 duckq에 넣어놓아야 한다.

		// 오리가 긁고 간 자리를 기억해두려면 별도의 큐가 필요함, 그건 비효율
		// 얼음이 녹을 때 오리가 갈 자리라면 오리 큐에 넣어둬야 함
		// 얼음이 녹을 때 중복 계산을 막기 위해 얼음에 visited를 한다

		day++;
	}
	cout << day;
}

3트인데도 안돼서 답지 보기로

📖 모두의 네트워크 기초

1장 네트워크 첫걸음

네트워크 : 컴퓨터랑 컴퓨터 연결하여 데이터 교환이나 협력하는 통신망

네트워크 사용 이유

주변 장치 공유 : 프린터 같은 거 연결
데이터 공유
공동 작업

랜(Local Area Network, LAN) : 건물 안이나 특정 지역을 범위로 하는 네트워크

star형 : 하나의 허브에 여러 대의 컴퓨터 연결. 확장 쉽지만 허브 터지면 통신 안됨.
ring형 : 개별 컴퓨터가 서로 원처럼 연결. 초기 구성 쉽지만 한 대 추가할 경우 링 절단하고 다시 연결해야함.
bus형 : 하나의 긴 선에 컴퓨터를 포함한 모든 주변장치 연결. 케이블 터지면 통신 안됨.

왠(Wide Area Network, WAN) : 2개 이상의 랜을 연결한 것

별도의 네트워크 접속 형태ㄹ는 없고 랜 사이 통신만 잘 이루어지게 하면 됨

네트워크 구성 장치

허브 : 여러 대의 컴퓨터 연결
스위치 : 대역폭 확대
라우터 : 컴퓨터 B를 찾아가기 위한 길 제시
브리지 : 2개 이상의 네트워크를 연결. 데이터를 한 곳에서 다른 곳으로 전달.

대역폭(bandwidth) : 1초당 처리할 수 있는 데이터 양, (용량 x 8) / 처리 시간으로 구한다.

데이터 처리 단위

1바이트 = 8비트
1킬로바이트 = 1024바이트
1메가바이트 = 10204메가바이트
1기가바이트 = 1024메가바이트
1테라바이트 = 1024기가바이트

2장 네트워크 통신을 위한 약속

프로토콜 : 통신할 때 메시지 주고받는 규칙

OSI 7계층(Open systems Interconnection 7 Layers)
TCP/IP 4 계층(Transmission Control Protocol/Internet Protocol 4 Layers)

OSI 7계층

응용 계층(Application Layer) : 사용자와 애플리케이션 간의 소통
표현 계층(Presentation Layer) : 데이터를 어떻게 표현할지 정의
세션 계층(Session Layer) : 통신을 설정,관리,종료
전송 계층(Transport Layer) : 신뢰성 있는 정확한 데이터 전달
네트워크 계층(Network Layer) : 네트워크 장치 간의 경로 선택과 데이터 전송. 라우터 필요
데이터 링크 계층(Data Link Layer) : 물리적인 연결을 통해 오류 없는 데이터 전달. 브리지, 스위치 필요
물리 계층(Physical Layer) : 전기 신호를 이용해서 통신 케이블로 데이터 전송. 리피터, 허브 필요

OSI 7계층 데이터 표현

응용,표현,세션 : 데이터, 메시지
전송 : 세그먼트
네트워크 : 패킷
데이터 링크 : 프레임
물리 : 비트

데이터에 든 거

데이터 : 이메일로 예를 들면 이메일의 본문
세그먼트 : 포트 번호. 전송 계층에서 추가.
패킷 : 송수신자 IP 주소. 네트워크 계층에서 추가.
프레임 : 송수신자 MAC 주소. 데이터 링크 계층에서 추가.

포트 번호 : 애플리케이션 구분하기 위한 번호
IP 주소 : 인터넷에 연결된 모든 장치를 구분하기 위한 고유 주소. 인터넷 서비스에 가입하면 할당받음. 네트워크 계층에서 사용.
MAC 주소 : 하드웨어 장치에 할당된 주소. 컴퓨터 구매할 때부터 할당됨. 데이터 링크 계층에서 사용.

TCP/IP 4 계층

OSI 7 너무 많아서 효율적인 사실상의 표준은 TCP/IP 4 계층
응용 계층 : 사용자와 애플리케이션 간의 소통
전송 계층 : 데이터의 전송 및 흐름에 있어 신뢰성 보장
인터넷 계층 : 물리적으로 데이터가 네트워크를 통해 어떻게 전송되는지를 정의
네트워크 인터페이스 계층 : 데이터를 전기 신호로 변환한 뒤 데이터 전송

헤더 : 각 계층을 지나면서 덧붙여지는 정보
캡슐화 : 헤더가 추가되는 과정
역캡슐화 : 헤더가 분리되는 과정

VPN(Virtual Private Network, 가상사설망)
1. VPN 클라 소프트웨어 설치
2. VPN 서버 연결 및 인증
3. 데이터 암호화
4. 터널링으로 암호화 데이터 전송

3장 물리 계층 : 데이터를 전기 신호로 변환하는 단계

랜 카드 : 데이터를 전기 신호로 변환
리피터 : 전기 신호를 증폭 (요즘엔 잘 안 씀)
허브 : 전송된 데이터 신호를 복원하고 증폭, 하나의 입력 신호를 여러 디바이스로 복제

4장 데이터 링크 계층 : MAC 주소로 통신하는 단계

데이터 계층 오류 감시 및 수정 방식

회선 제어 : 오류 회피하여 신호 간 충돌 현상 발생하지 않게 한다.
- 신호 시작인 ENQ(Enquiry)와 신호 끝인 EOT(End of Transmission)를 명시적 지정
오류 제어 : 외부 간섭, 시간 지연 등 오류 검출하고 정정
- 패리티 검사(parity check) : 수신자에게 보내는 최종 데이터의 1의 개수를 짝수로 보낼지 홀수로 보낼지 미리 약속하고 여분의 비트를 채워 보냄
- CRC(Cyclic Redundancy Check) : 데이터에 CRC 코드를 추가하여 오류를 감지. 송신자가 코드 생성하고 수신자도 동일 계산 수행하여 일치 확인
- 검사합 : 송수신자가 데이터와 관련된 검사합 계산하여 일치 확인
- 해밍 코드(Hamming code) : 데이터에 추가적인 패리티 비트 포함
  -흐름 제어 : 수신자 상황에 따라 송신자 데이터 전송 조절하여 송수신자 데이터 처리 속도 차이 해결
- 정지-대기(Stop & Wait) : 송신자가 데이터 하나 전송 후 다음 데이터 전달 전 확인 응답 기다림

이더넷(Ethernet) : 다수의 컴퓨터, 허브, 스위치를 하나의 인터넷 케이블에 연결한 네트워크 구조

CSMA/CD(Carrier Sense Multiple Access/Collision Detection) 프로토콜 사용
2대 이상의 컴퓨터가 동시에 데이터 보내는 충돌(collision) 방지하기 위해 전류 강도 확인해 케이블 사용중인지 확인하는 CSMA/CD 방식 사용
현재 CSMA/CD는 잘 사용 안 함. OSI 7 계층 중 2계층인 스위치 장비가 그 역할을 대신.

MAC(Media Access Control) 주소 : 랜 카드에 할당된 값. 전 세계에서 하나만 존재.

상위 24비트 : OUI, 랜 카드 제조사 코드
이후 24비트 : UAA, 제조사가 랜카드에 부여한 번호

프레임

이더넷 헤더
- 목적지 MAC 주소
- 출발지 MAC 주소
- 유형 : IPv4, IPv6, ARP(Address Resolution Protocol, IP 주소에 해당하는 MAC 주소 알고자할 때 사용하는 프로토콜)
데이터
트레일러

ARP로 MAC 주소 알아내는 과정 (기본적으론 LAN에서만 가능, WAN 환경에선 라우터 장비 거쳐야 확인 가능)
1. 컴퓨터 A가 같은 허브에 묶인 모든 컴퓨터에게 특정 IP 주소의 MAC 주소 물음.

Broadcast : 모든 컴퓨터에게 질의
ARP Request : MAC 주소 묻기

모든 컴퓨터가 자신의 IP를 그 주소와 비교하고, 해당되는 컴퓨터 B가 MAC 주소를 전달함.

ARP Table : 컴퓨터 A가 컴퓨터 B의 IP와 MAC 주소를 메모리에 저장

컴퓨터 A가 컴퓨터 B의 MAC 주소 알게 됐으므로 통신 가능

스위치

연결된 모든 장치에 데이터 전송하는 허브와 다르게 필요한 장치에만 데이터 전달하는 장치
소규모 네트워크 안에서 컴퓨터, 프린터 등 모든 장치를 서로 연결해서 데이터를 쉽게 공유
MAC 테이블에 스위치에 연결된 컴퓨터의 MAC 주소 관리
Flooding : MAC 주소 업뎃을 위해 스위치에 물려있는 모든 컴퓨터에 데이터 보내는 것. MAC 테이블에 이미 있으면 안 하고 바로 연결해줌.

단방향 통신 : 일방적으로 데이터 전송
양방향 통신 : 하나의 통신 채널에서 송수신이 모두 가능

반이중(Half Duplex) 방식 : 양쪽 방향에서 통신 가능하지만 동시에 통신은 불가
- 송수신을 번갈아가며 통신하여 데이터 전송 속도 빠름
- 주로 허브에서 사용
- 채널을 하나만 사용하여 충돌 문제가 남아있음
전이중(Full Duplex) 방식 : 채널을 2개 두어서 양쪽 방향에서 동시에 데이터 주고 받음
- 스위치에서 사용됨
- 충돌 문제 해결됨

충돌 도메인 : 충돌이 발생할 때 그 영향이 미치는 범위. 하나의 허브에 컴퓨터들이 연결돼있으면 여기 연결된 모든 컴퓨터가 충돌 도메인.