열쇠

[hye-on]

🔗 열쇠

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>


using namespace std;

int t, r, c;
string map[100];
bool visit[100][100];
string key;

int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
int ans;

void removeDoor(char key, queue<pair<int, int>>&q) {

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (tolower(map[i][j]) == key) {
				map[i][j] = '.';
				if(visit[i][j])
					q.push({ i, j });
				
			}
		}
	}
}

void bfs(queue<pair<int, int>>&q) {
	queue<pair<int, int>>tq;
	while (!q.empty()) {
		
		int curY = q.front().first;
		int curX = q.front().second;
		q.pop();
	
		for (int i = 0; i < 4; i++) {
			int ny = curY + dy[i];
			int nx = curX + dx[i];
			
			if (ny >= r || ny < 0 || nx >= c || nx < 0 || visit[ny][nx])
				continue;
		

			if (map[ny][nx] == '.') {
				q.push({ ny, nx });
				visit[ny][nx] = true;
			}
			else if (map[ny][nx] <= 'Z' && map[ny][nx] >= 'A') {
				visit[ny][nx] = true;
			}
			else if (map[ny][nx] == '$') {

				ans++;
				q.push({ ny, nx });
				visit[ny][nx] = true;
			}
			else if (map[ny][nx] <= 'z' && map[ny][nx] >= 'a') {
				q.push({ ny, nx });		
				removeDoor(map[ny][nx],q);
				visit[ny][nx] = true;
			}


		}
	}
}


int main() {
	cin >> t;
	while (t--) {
		ans = 0;
		memset(visit, false, sizeof(visit));


		cin >> r >> c;
		for (int i = 0; i < r; i++) {
			cin >> map[i];
			
		}
		cin >> key;
		queue<pair<int, int>>tempQ;
		if (key != "0") {
			for (int i = 0; i < key.size(); i++) {
				removeDoor(key[i],tempQ);		
			}
		}
		queue<pair<int, int>>q;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (i == 0 || i == r - 1 || j == 0 || j == c - 1) {
					
					//들어갈 수 있는 입구를 q에 넣어준다.
					if ('a' <= map[i][j] && map[i][j] <= 'z') {
						removeDoor(map[i][j], tempQ);
						visit[i][j] = true;
						q.push({ i,j });
					}
					if ('A' <= map[i][j] && map[i][j] <= 'Z') {
						visit[i][j] = true;
					}
					else if (map[i][j] == '.') {
						visit[i][j] = true;
						q.push({ i,j });
					}
					else if (map[i][j] == '$') {
						visit[i][j] = true;
						q.push({ i,j });
						ans++;

					}
					
				}
			}
			

		}

		while (!tempQ.empty()) {

			int y = tempQ.front().first;
			int x = tempQ.front().second;

			tempQ.pop();

			if(y == 0 || y== r-1 || x==0 || x==c-1){
				visit[y][x] = true;
				q.push({ y,x });
			}
		}

		if (q.size() == 0)
			cout << '0' << "\n";
		else {
			bfs(q);
			cout<< ans << "\n";
		}
		
	}
}

코멘트

- 조건 챙기기 까다로웠던 것 같습니다.

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

import java.io.*;
import java.util.*;
import java.util.concurrent.*;

// 20:05 시작!
public class Main
{
    static int h, w, count;
    static char[][] map;
    static boolean[][] visit;
    static Set<Character> keys;
    static Map<Character, List<Integer>> doors;
	public static void main(String[] args) throws Exception {
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	    int t = Integer.parseInt(bf.readLine());
	    
	    StringTokenizer st;
	    StringBuilder sb = new StringBuilder();
	    while(t > 0) {
	        st = new StringTokenizer(bf.readLine());
	        h = Integer.parseInt(st.nextToken());
	        w = Integer.parseInt(st.nextToken());
	        count = 0;
	        visit = new boolean[h][w];
	        doors = new ConcurrentHashMap<>();
	        
	        map = new char[h][w];
	        for(int i = 0; i < h; ++i) {
	            map[i] = bf.readLine().toCharArray();
	        }
	        
	        keys = new HashSet<>();
	        for(char key : bf.readLine().toCharArray()) {
	            if(key == '0') break;
	            keys.add(key);
	        }
	        
	        // 테두리 탐색
	        int[] xs = new int[]{ 0, h - 1 };
	        for(int y = 0; y < w; ++y) {
	            for(int i = 0; i < 2; ++i) {
	                int x = xs[i];
	                
	                if(visit[x][y]) continue;
	                if(map[x][y] == '*') continue;
	                
	                visit[x][y] = true;
	                
	                if(map[x][y] >= 'A' && map[x][y] <= 'Z'
	                    && !keys.contains(Character.toLowerCase(map[x][y]))) {
	                    doors.putIfAbsent(map[x][y], new ArrayList<>());
	                    doors.get(map[x][y]).add(getNum(x, y));
	                    continue;
	                }
	                
	                if(map[x][y] == '$') {
	                    count++;
	                }
	                
	                if(map[x][y] >= 'a' && map[x][y] <= 'z') {
	                    keys.add(map[x][y]);
	                }
	                
	                search(x, y);
	            }
	        }
	        
	        int[] ys = new int[]{ 0, w - 1 };
	        for(int x = 1; x < h - 1; ++x) {
	            for(int i = 0; i < 2; ++i) {
	                int y = ys[i];
	                
	                if(visit[x][y]) continue;
	                if(map[x][y] == '*') continue;
	                
	                visit[x][y] = true;
	                
	                if(map[x][y] >= 'A' && map[x][y] <= 'Z'
	                    && !keys.contains(Character.toLowerCase(map[x][y]))) {
	                    doors.putIfAbsent(map[x][y], new ArrayList<>());
	                    doors.get(map[x][y]).add(getNum(x, y));
	                    continue;
	                }
	                
	                if(map[x][y] == '$') {
	                    count++;
	                }
	                
	                if(map[x][y] >= 'a' && map[x][y] <= 'z') {
	                    keys.add(map[x][y]);
	                }
	                
	                search(x, y);
	            }
	        }
	        
	        Set<Character> already = new HashSet<>();
	        List<Character> list;
	        while(keys.size() > already.size()) {
	            list = new ArrayList<>();
	            for(char key : keys) {
	                if(already.contains(key)) continue;
	                list.add(key);
	                already.add(key);
	            }
	            
	            for(char key: list) {
	                for(int door : doors.getOrDefault(Character.toUpperCase(key), new ArrayList<>())) {
	                    int[] point = getPoint(door);
	                    search(point[0], point[1]);
	                }
	            }
	        }
	        
	        sb.append(count).append("\n");
	        
	        --t;
	    }
	    
	    System.out.println(sb);
	}
	
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	public static void search(int x, int y) {
        for(int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && nx < h && ny >= 0 && ny < w && !visit[nx][ny]) {
                
                if(map[nx][ny] == '*') continue;
                
                visit[nx][ny] = true;
                
                if(map[nx][ny] >= 'A' && map[nx][ny] <= 'Z'
                    && !keys.contains(Character.toLowerCase(map[nx][ny]))) {
                    doors.putIfAbsent(map[nx][ny], new ArrayList<>());
                    doors.get(map[nx][ny]).add(getNum(nx, ny));
                    continue;
                }
                
                if(map[nx][ny] == '$') {
                    count++;
                }
                
                if(map[nx][ny] >= 'a' && map[nx][ny] <= 'z') {
                    keys.add(map[nx][ny]);
                }

                search(nx, ny);
            }
        }
	}

	public static int getNum(int x, int y) {
	    return x * w + y;
	}
	
	public static int[] getPoint(int num) {
	    int x = num / w;
	    int y = num - (x * w);
	    return new int[]{ x, y };
	}
}

코멘트

- 하.. ConcurrentModification 에러 때문에 진짜 머리 아팠습니다..😢 중복 코드 줄일 수 있을 것 같긴한데.. 다음에 도전해보겠습니다!