✅ What I did today
- 백준
⚔️ 백준
2206 벽 부수고 이동하기
틀린 풀이
#include"2206.h"
using namespace std;
typedef pair<int, int> pii;
// try1 : 모든 벽 한 번씩 없애보고 bfs
// 실수
// 1. wallq pop을 빼먹음
// 2. 방문을 체크 안해서 무한 bfs 돌아버림
// 3. while에 조건문을 잘못 삽입해서 무한 반복해버림
// 결과 : 시간 초과
// try2 : 0과 연결된 벽만 한 번씩 없애보고 bfs 시도
// 결과 : 시간 초과
// try3 : 입력 최적화
// 결과 : 시간 초과
// try4 : 0,0과 연결된 벽들만 없애보기
// 실수
// 1. bfs를 했어야 했는데 입구 오른쪽하고 아래쪽만 확인해봄
// 결과 : 시간 초과
// try5 : 0,0에서 bfs 해보고 안되면 끝점에서 bfs해보고 set에 동일한 벽 있는지 확인
// 결과 : 시간 초과
// try6 : char 대신 int를 비교하도록 변환
// 결과 : 시간 초과
// try 7 : 답지 보고 접근 방식 배우기
void B2206::Solution()
{
// 시작은 0,0이 아니라 (1,1)이라고 표현한 것 주의
cin.tie(0); ios::sync_with_stdio(false);
vector<int> dx = { 1,-1,0,0 };
vector<int> dy = { 0,0,1,-1 };
int N, M;
cin >> N >> M;
vector<vector<int>> mmap(N,vector<int>(M));
vector<vector<bool>> visited(N, vector<bool>(M));
queue<pii> roomq;
queue<pii> wallq;
set<pii> wallset;
string s;
for (int i = 0; i < N; ++i) {
cin >> s;
for (int j = 0; j < M; ++j) {
mmap[i][j] = s[j] - '0';
}
}
// 후보 벽 고르는 과정
roomq.push({ 0,0 });
while (!roomq.empty())
{
pii room = roomq.front(); roomq.pop();
int roomx = room.first, roomy = room.second;
for (int i = 0; i < 4; ++i) {
int newx = roomx+dx[i], newy = roomy+dy[i];
if (0 <= newx && newx < N && 0 <= newy && newy < M
&& !visited[newx][newy])
{
if (mmap[newx][newy] == 0) {
roomq.push({ newx,newy });
}
else {
wallset.insert({ newx,newy });
}
visited[newx][newy] = true;
}
}
}
visited = vector<vector<bool>>(N, vector<bool>(M));
roomq.push({ N-1,M-1 });
while (!roomq.empty())
{
pii room = roomq.front(); roomq.pop();
int roomx = room.first, roomy = room.second;
for (int i = 0; i < 4; ++i) {
int newx = roomx + dx[i], newy = roomy + dy[i];
if (0 <= newx && newx < N && 0 <= newy && newy < M
&& !visited[newx][newy])
{
if (mmap[newx][newy] == 0) {
roomq.push({ newx,newy });
}
else if (wallset.count({newx,newy})) {
wallq.push({ newx,newy });
}
visited[newx][newy] = true;
}
}
}
// 후보 벽 한 번씩 지워보고 bfs 반복
int min_count = numeric_limits<int>::max();
while (!wallq.empty())
{
pii wall = wallq.front(); wallq.pop();
int wallx = wall.first, wally = wall.second;
mmap[wallx][wally] = 0;
int count = 1;
bool found = false;
queue<pii> bfsq;
visited = vector<vector<bool>>(N, vector<bool>(M));
bfsq.push({ 0,0 }); visited[0][0] = true;
while (!bfsq.empty())
{
count++;
int qlen = bfsq.size();
for (int i = 0; i < qlen; ++i)
{
int x = bfsq.front().first, y = bfsq.front().second;
bfsq.pop();
for (int k = 0; k < 4; ++k) {
int newx = x + dx[k];
int newy = y + dy[k];
if (0 <= newx && newx < N && 0 <= newy && newy < M
&& !visited[newx][newy] && mmap[newx][newy] == 0) {
if (newx == N-1 && newy == M-1) {
found = true; break;
}
bfsq.push({ newx,newy });
visited[newx][newy] = true;
}
}
}
if (found) { break; }
}
if (found) {
min_count = min(min_count, count);
}
mmap[wallx][wally] = 1;
}
if (min_count == numeric_limits<int>::max()) {
cout << -1;
}
else {
cout << min_count;
}
}맞은 풀이
벽이 늘어나면 탐색할 칸도 줄어드니까 될 줄 알았고, 최적화도 빡세게 했는데 안되는 건 안되는 거였다.
정답 방식대로 하면 불필요한 중복 bfs 연산이 줄어들고, 같은 연산하는 건 합쳐진다.
좌표를 넣으면서 상태도 같이 넣어주면 될듯
#include"2206.h"
using namespace std;
typedef tuple<int,int,bool> tiib;
// try1 : 모든 벽 한 번씩 없애보고 bfs
// 실수
// 1. wallq pop을 빼먹음
// 2. 방문을 체크 안해서 무한 bfs 돌아버림
// 3. while에 조건문을 잘못 삽입해서 무한 반복해버림
// 결과 : 시간 초과
// try2 : 0과 연결된 벽만 한 번씩 없애보고 bfs 시도
// 결과 : 시간 초과
// try3 : 입력 최적화
// 결과 : 시간 초과
// try4 : 0,0과 연결된 벽들만 없애보기
// 실수
// 1. bfs를 했어야 했는데 입구 오른쪽하고 아래쪽만 확인해봄
// 결과 : 시간 초과
// try5 : 0,0에서 bfs 해보고 안되면 끝점에서 bfs해보고 set에 동일한 벽 있는지 확인
// 결과 : 시간 초과
// try6 : char 대신 int를 비교하도록 변환
// 결과 : 시간 초과
// try 7 : 답지 보고 destroyed 도입한 bfs 한 번
// 결과 : 틀렸습니다
// try 8 :
// 수정
// 이전 반례 : ㄷ자 통로가 있을 때, 통로를 지난 후에 벽을 부숴야
// 목표에 도달 가능하다면 destroyed가 먼저 visited 처리를 해버리면 안됨
void B2206::Solution()
{
// 시작은 0,0이 아니라 (1,1)이라고 표현한 것 주의
cin.tie(0); ios::sync_with_stdio(false);
vector<int> dx = { 1,-1,0,0 };
vector<int> dy = { 0,0,1,-1 };
int N, M;
cin >> N >> M;
vector<vector<int>> mmap(N,vector<int>(M));
vector<vector<bool>> visited(N, vector<bool>(M));
vector<vector<bool>> visited_d(N, vector<bool>(M));
string s;
for (int i = 0; i < N; ++i) {
cin >> s;
for (int j = 0; j < M; ++j) {
mmap[i][j] = s[j] - '0';
}
}
// int = index, bool = 벽 부쉈는지
int count = 0;
bool found = false;
queue<tiib> q;
q.push(make_tuple(0,0,false));
while (!q.empty())
{
count++;
int qlen = q.size();
for (int i = 0; i < qlen; ++i) {
int x, y; bool destroyed;
tie(x, y, destroyed) = q.front(); q.pop();
if (x == N - 1 && y == M - 1) {
found = true;
break;
}
for (int i = 0; i < 4; ++i) {
int newx = x + dx[i];
int newy = y + dy[i];
if (0 <= newx && newx < N && 0 <= newy && newy < M) {
if (destroyed) {
if (visited_d[newx][newy]) continue;
if (mmap[newx][newy] == 0) {
q.push(make_tuple(newx, newy, destroyed));
}
visited_d[newx][newy] = true;
}
else {
if (visited[newx][newy]) continue;
if (mmap[newx][newy] == 1) {
q.push(make_tuple(newx,newy,true));
}
else if (mmap[newx][newy] == 0) {
q.push(make_tuple(newx, newy, destroyed));
}
visited[newx][newy] = true;
}
}
}
}
if (found) break;
}
if (found) cout << count;
else cout << -1;
}- bfs를 따로 함수로 빼면 플래그 선언할 필요 없이 return 때리면 바로 탈출한다
1865 웜홀
#include"1865.h"
using namespace std;
// 실수 1. 또 인덱스랑 실제 번호랑 헷갈림. 공간 더 줬어야 했음.
// 실수 2. 행렬 초기화를 안 함.
// 실수 3. 행렬 초기화를 int max로 했더니 오버플로우 발생함.
// 실수 4. 문제를 대충 읽어서 도로는 무향, 웜홀은 유향인거 놓침
// 실수 5. 문제를 덜 읽어서 도로가 중복일 수 있는거 놓침
// 실수 6. 웜홀은 시간이 (-)인데 (+)로 넣어버림
// 실수 7. mat[E][S] = min(T, mat[S][E]); 복붙하다 인덱스 실수
// 실수 8. 테케가 다를 때 웜홀 벡터 초기화를 안 해줌
// 웜홀은 도로와 별개라고 생각했는데,
// 도로와 연계하여 이동하는 경우도 있으니 음수 가중치 도로로 간주해야 할듯.
void B1865::Solution()
{
const int INF = 10001;
int TC, N, M, W;
cin >> TC;
while (TC--)
{
cin >> N >> M >> W;
vector<vector<int>> mat(N+1,vector<int>(N+1,INF));
vector<tuple<int, int, int>> wormhole = {};
int S, E, T;
for (int i = 0; i < M; ++i) {
cin >> S >> E >> T;
// S에서 E로 가는데 T의 시간이 걸린다
mat[S][E] = min(T, mat[S][E]);
mat[E][S] = min(T, mat[E][S]);
}
for (int i = 0; i < W; ++i) {
cin >> S >> E >> T;
mat[S][E] = min(-T, mat[S][E]);
wormhole.push_back(make_tuple(S, E, T));
}
// 플로이드 워셜로 모든 정점 사이 거리 확인
for (int i = 1; i < N+1; ++i) {
for (int j = 1; j < N+1; ++j) {
for (int k = 1; k < N+1; ++k) {
mat[j][k] = min(mat[j][k], mat[j][i] + mat[i][k]);
}
}
}
// 모든 웜홀 확인
bool found = false;
for (auto tup : wormhole) {
tie(S, E, T) = tup;
if (mat[E][S] < T) {
found = true;
break;
}
}
if (found) { cout << "YES" << endl; }
else { cout << "NO" << endl; }
}
}
너 정말 **핵심**을 찔렀어